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.
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:
This code defines a struct DSU representing the Disjoint-Set Union data structure for managing connected components. The functions createDSU, find, and unionSet handle initialization, set finding, and union operations, respectively.
The main function, maxNumEdgesToRemove, processes the edges by type. Type 3 edges are processed first because they serve both Alice and Bob. Then type 1 and 2 edges are processed separately for Alice’s and Bob’s connectivity. The variable savedEdges stores the number of redundant edges found. After processing, checking the number of connected components in alice and bob determines if the graph is fully traversable, and returns the maximum 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.
| 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 |
Remove Max Number of Edges to Keep Graph Fully Traversable - Leetcode 1579 - Python • NeetCodeIO • 13,672 views views
Watch 9 more video solutions →Practice Remove Max Number of Edges to Keep Graph Fully Traversable with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor