Watch 10 video solutions for Remove Max Number of Edges to Keep Graph Fully Traversable, a hard level problem involving Union Find, Graph. This walkthrough by NeetCodeIO has 13,672 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Alice and Bob have an undirected graph of n nodes and three types of edges:
Given an array edges where edges[i] = [typei, ui, vi] represents a bidirectional edge of type typei between nodes ui and vi, find the maximum number of edges you can remove so that after removing the edges, the graph can still be fully traversed by both Alice and Bob. The graph is fully traversed by Alice and Bob if starting from any node, they can reach all other nodes.
Return the maximum number of edges you can remove, or return -1 if Alice and Bob cannot fully traverse the graph.
Example 1:
Input: n = 4, edges = [[3,1,2],[3,2,3],[1,1,3],[1,2,4],[1,1,2],[2,3,4]] Output: 2 Explanation: If we remove the 2 edges [1,1,2] and [1,1,3]. The graph will still be fully traversable by Alice and Bob. Removing any additional edge will not make it so. So the maximum number of edges we can remove is 2.
Example 2:
Input: n = 4, edges = [[3,1,2],[3,2,3],[1,1,4],[2,1,4]] Output: 0 Explanation: Notice that removing any edge will not make the graph fully traversable by Alice and Bob.
Example 3:
Input: n = 4, edges = [[3,2,3],[1,1,2],[2,3,4]] Output: -1 Explanation: In the current graph, Alice cannot reach node 4 from the other nodes. Likewise, Bob cannot reach 1. Therefore it's impossible to make the graph fully traversable.
Constraints:
1 <= n <= 1051 <= edges.length <= min(105, 3 * n * (n - 1) / 2)edges[i].length == 31 <= typei <= 31 <= ui < vi <= n(typei, ui, vi) are distinct.Problem Overview: You are given a graph where edges can be used by Alice, Bob, or both. The goal is to remove the maximum number of edges while ensuring both Alice and Bob can still traverse the entire graph. If either cannot reach all nodes, return -1.
Approach 1: Edge Removal with Connectivity Check (DFS/BFS) (Time: O(E * (V + E)), Space: O(V))
Start with the full graph and attempt removing each edge one by one. After removing an edge, run a connectivity check for Alice and Bob separately using DFS or BFS. If both graphs remain fully connected, the edge is unnecessary and can stay removed; otherwise restore it. This brute-force method works conceptually but is extremely expensive because each removal requires a full traversal of the graph. It demonstrates the problem constraint: connectivity must be preserved for two different users.
Approach 2: Union-Find with Prioritized Edge Inclusion (Time: O(E α(N)), Space: O(N))
The optimal solution treats the problem like a connectivity construction task. Use Union-Find (Disjoint Set Union) to track connected components. Edges of type 3 (usable by both Alice and Bob) provide the most value, so process them first and union nodes in both DSU structures simultaneously. Then process type 1 edges for Alice’s DSU and type 2 edges for Bob’s DSU. If a union operation fails because the nodes are already connected, the edge is redundant and can be counted as removable.
The key insight: prioritize shared edges to maximize reuse across both traversals. If you used separate edges first, you might miss opportunities where one edge satisfies both graphs. This greedy ordering guarantees the minimum edges required to keep both graphs connected. The algorithm relies on efficient component merging from graph connectivity theory and the near-constant amortized cost of DSU operations.
After processing all edges, verify that both DSU structures have exactly one connected component. If either graph is disconnected, return -1. Otherwise, the count of redundant edges represents the maximum number of removable edges.
Recommended for interviews: The Union-Find greedy strategy is the expected solution. Interviewers want to see you recognize the similarity to Kruskal-style edge selection and apply prioritized processing of shared edges. Mentioning the brute-force connectivity check shows understanding of the constraints, but implementing the optimized DSU approach demonstrates strong algorithmic design.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Edge Removal + DFS/BFS Connectivity Check | O(E * (V + E)) | O(V) | Conceptual baseline or when demonstrating brute-force reasoning in interviews |
| Union-Find with Prioritized Edge Inclusion | O(E α(N)) | O(N) | Optimal solution for large graphs; standard interview and competitive programming approach |
| Dual DSU with Kruskal-Style Processing | O(E α(N)) | O(N) | Alternative implementation of the same idea emphasizing MST-style edge selection |