Sponsored
Sponsored
This approach utilizes the Union-Find (or Disjoint Set Union, DSU) data structure to manage the connectivity of nodes. The critical idea is to process edge types in a specific order to ensure that both Alice and Bob can fully traverse the graph while maximizing the number of removable edges:
Time Complexity: O(E * α(n)), where E is the number of edges and α(n) is the inverse Ackermann function, effectively constant.
Space Complexity: O(n) for storing the disjoint sets for both Alice and Bob.
1import java.util.*;
2
3class DSU {
4 private int[] parent, rank;
5 public
This Java solution leverages a DSU to keep track of connected components efficiently. The main class DSU has methods find and union to manage connectivity alongside a useful connected method to verify full connectivity.
The core process involves checking type 3 edges that can be leveraged by both users, aiming to maximize their usage. After including type-specific edges for Alice and Bob as necessary, it checks connectivity. If either Alice or Bob ends up with disconnected components, the function returns -1, otherwise, it outputs the number of edges that can be removed safely.