Leetcode 1579 - Remove Max Number of Edges to Keep Graph Fully Traversable [30/6/24]

Time Taken: More than 1hr
Tag: LeetCode Hard
Concept: ufds/Disjoint Set
Basic ideas:
- Keep a ufds for Alice and Bob respectively. The purpose of disjoint set is to keep track of the nodes that are connected (can reach each other starting from any node).
- Iterate through edges vector. Since type 3 edges cover both Alice and Bob, we want to greedily consider these edges over type 1 or type 2 edges. We add edge into consideration if disjoint set does not have both nodes connected yet for at least 1 of Alice or Bob.
- We use the idea of “constructing” edges (instead of “removing” edges) by adding effective edges to the number of edges taken in final answer represented by “ans”.
- Go through edges vector once more to consider the “lower-priority” types 1 and 2 edges.
- Check if graph is fully traversable by Alice and Bob using “numDisjointComponents” as a property of DisjointSet class.
- “numDisjointComponents” == 1 for graph to be fully traversable.
- Return -1 if not fully traversable by both Alice and Bob
- Else return the maximum number of edges that can be removed, edges.size() - ans”