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.The key idea for #1579 Remove Max Number of Edges to Keep Graph Fully Traversable is to keep the graph fully traversable for both Alice and Bob while removing as many redundant edges as possible. Since some edges can be used by both players, the optimal strategy is to process those shared edges first.
A common solution uses the Union-Find (Disjoint Set Union) data structure to efficiently track connectivity. First, apply type 3 edges (usable by both Alice and Bob) because they provide the most value. Then process type 1 edges for Alice and type 2 edges for Bob separately using their own union-find structures.
If an edge connects nodes that are already in the same component, it is redundant and can be removed. After processing all edges, verify that both Alice's and Bob's graphs are fully connected. This greedy + union-find approach keeps operations efficient with near-constant amortized time.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Union-Find with Greedy Edge Processing | O(E * α(N)) | O(N) |
NeetCodeIO
Use these hints if you're stuck. Try solving on your own first.
Build the network instead of removing extra edges.
Suppose you have the final graph (after removing extra edges). Consider the subgraph with only the edges that Alice can traverse. What structure does this subgraph have? How many edges are there?
Use disjoint set union data structure for both Alice and Bob.
Always use Type 3 edges first, and connect the still isolated ones using other edges.
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.
1class DSU {
2 constructor(n) {
3 this.parent = Array.from({ length: n }
The JavaScript version employs a class DSU to manage node connectivity using union-find principles. The function maxNumEdgesToRemove processes the input edge array in stages.
Initially, shared edges (type 3) are prioritized for connectivity with other types handled subsequently for each graph's completeness. A set is used to verify the number of distinct components each DSU represents; ideally, this should output just one, indicative of a fully connected graph.
The graph is traversed, counting redundant (unnecessary) edges, returning this count unless incomplete connectivity is found, where it returns -1.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Type 3 edges benefit both Alice and Bob, so using them first maximizes shared connectivity. This reduces the need for separate edges later and increases the number of removable redundant edges.
Yes, this type of problem is common in FAANG-style interviews because it tests graph fundamentals, greedy decision-making, and proficiency with Union-Find. Candidates are expected to reason about connectivity and optimization.
Union-Find (Disjoint Set Union) is the best data structure for this problem. It efficiently tracks connected components and helps detect whether adding an edge creates redundancy, enabling near-constant time connectivity checks.
The optimal approach uses a greedy strategy combined with the Union-Find (Disjoint Set Union) data structure. Shared edges are processed first to maximize connectivity for both Alice and Bob. Then individual edges are applied while counting redundant edges that can be removed.