# Remove Max Number of Edges to Keep Graph Fully Traversable
**Difficulty:** HARD
[External](https://leetcode.com/problems/remove-max-number-of-edges-to-keep-graph-fully-traversable)
Canonical: https://scaleengineer.com/dsa/problems/remove-max-number-of-edges-to-keep-graph-fully-traversable
**Algorithms:** [Union Find](https://scaleengineer.com/algorithms/union-find)
**Data structures:** Graph
---
## Problem
Alice and Bob have an undirected graph of `n` nodes and three types of edges:

* Type 1: Can be traversed by Alice only.
* Type 2: Can be traversed by Bob only.
* Type 3: Can be traversed by both Alice and Bob.

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:**

**![](https://assets.glich.co/dsa/remove-max-number-of-edges-to-keep-graph-fully-traversable/image0.png)**

**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:**

**![](https://assets.glich.co/dsa/remove-max-number-of-edges-to-keep-graph-fully-traversable/image1.png)**

**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:**

**![](https://assets.glich.co/dsa/remove-max-number-of-edges-to-keep-graph-fully-traversable/image2.png)**

**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 <= 105`
* `1 <= edges.length <= min(105, 3 * n * (n - 1) / 2)`
* `edges[i].length == 3`
* `1 <= typei <= 3`
* `1 <= ui < vi <= n`
* All tuples `(typei, ui, vi)` are distinct.

# Approaches
## Greedy Approach with Graph Traversal (BFS/DFS)
This approach also follows the same greedy strategy of prioritizing Type 3 edges, then Type 1 for Alice, and Type 2 for Bob. However, instead of using a specialized data structure like Union-Find to check for connectivity and cycles, it builds the graphs for Alice and Bob explicitly using adjacency lists and performs a graph traversal (like Breadth-First Search or Depth-First Search) for each potential edge to see if it's necessary.
**Time:** `O(E * (N + E))`. For each of the `E` edges, we perform a traversal to check for connectivity. The traversal takes `O(N + K)` where `K` is the number of edges currently in the graph. In the worst case, `K` is `O(E)`, leading to `O(N + E)` per check. This results in a total time complexity of `O(E * (N + E))`. · **Space:** `O(N + E)` to store the adjacency lists for both Alice's and Bob's graphs.
**Pros:** Conceptually straightforward, relying on basic graph traversal algorithms.; Avoids the need for a more complex data structure like Union-Find.
**Cons:** Very inefficient. The repeated traversals lead to a high time complexity.; For large graphs, this approach will be too slow and likely result in a "Time Limit Exceeded" error.
### Explanation
We maintain two separate graphs, `graph_alice` and `graph_bob`, represented by adjacency lists. The goal is to add the minimum number of edges to make both graphs connected.
1.  **Process Type 3 Edges:** Iterate through all Type 3 edges. For each edge `(u, v)`, we first check if `u` and `v` are already connected in the current `graph_alice`. This check is done by starting a traversal (e.g., BFS) from `u` and seeing if `v` is reachable. If they are not connected, we add the edge to both `graph_alice` and `graph_bob` and increment a counter for used edges.
2.  **Process Type 1 Edges:** Next, iterate through Type 1 edges. For each edge `(u, v)`, we check for connectivity only in `graph_alice`. If `u` and `v` are not connected in `graph_alice`, we add the edge to it and increment the used edges count.
3.  **Process Type 2 Edges:** Similarly, for each Type 2 edge `(u, v)`, we check for connectivity in `graph_bob`. If they are not connected, we add the edge to `graph_bob` and increment the used edges count.
After considering all edges, we perform a final check. We run a traversal on `graph_alice` starting from an arbitrary node (e.g., node 1) and count the visited nodes. If the count is not `n`, Alice's graph is not fully traversable. We do the same for `graph_bob`. If both graphs are fully connected, we return `total_edges - edges_used`. Otherwise, it's impossible, so we return -1.
```java
import java.util.*;

class Solution {
    public int maxNumEdgesToRemove(int n, int[][] edges) {
        List<List<Integer>> aliceAdj = new ArrayList<>();
        List<List<Integer>> bobAdj = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            aliceAdj.add(new ArrayList<>());
            bobAdj.add(new ArrayList<>());
        }

        int edgesUsed = 0;

        // Process Type 3 edges
        for (int[] edge : edges) {
            if (edge[0] == 3) {
                if (!isConnected(aliceAdj, edge[1], edge[2], n)) {
                    aliceAdj.get(edge[1]).add(edge[2]);
                    aliceAdj.get(edge[2]).add(edge[1]);
                    bobAdj.get(edge[1]).add(edge[2]);
                    bobAdj.get(edge[2]).add(edge[1]);
                    edgesUsed++;
                }
            }
        }

        // Process Type 1 edges
        for (int[] edge : edges) {
            if (edge[0] == 1) {
                if (!isConnected(aliceAdj, edge[1], edge[2], n)) {
                    aliceAdj.get(edge[1]).add(edge[2]);
                    aliceAdj.get(edge[2]).add(edge[1]);
                    edgesUsed++;
                }
            }
        }

        // Process Type 2 edges
        for (int[] edge : edges) {
            if (edge[0] == 2) {
                if (!isConnected(bobAdj, edge[1], edge[2], n)) {
                    bobAdj.get(edge[1]).add(edge[2]);
                    bobAdj.get(edge[2]).add(edge[1]);
                    edgesUsed++;
                }
            }
        }

        if (isFullyConnected(aliceAdj, n) && isFullyConnected(bobAdj, n)) {
            return edges.length - edgesUsed;
        }

        return -1;
    }

    // Checks if two nodes are connected using BFS
    private boolean isConnected(List<List<Integer>> adj, int u, int v, int n) {
        Queue<Integer> queue = new LinkedList<>();
        boolean[] visited = new boolean[n + 1];
        queue.offer(u);
        visited[u] = true;
        while (!queue.isEmpty()) {
            int curr = queue.poll();
            if (curr == v) return true;
            for (int neighbor : adj.get(curr)) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    queue.offer(neighbor);
                }
            }
        }
        return false;
    }

    // Checks if the entire graph is connected
    private boolean isFullyConnected(List<List<Integer>> adj, int n) {
        if (n == 0) return true;
        Queue<Integer> queue = new LinkedList<>();
        boolean[] visited = new boolean[n + 1];
        int count = 0;
        
        queue.offer(1);
        visited[1] = true;
        count++;

        while (!queue.isEmpty()) {
            int curr = queue.poll();
            for (int neighbor : adj.get(curr)) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    queue.offer(neighbor);
                    count++;
                }
            }
        }
        return count == n;
    }
}
```
### Algorithm
- Initialize two adjacency lists, `aliceAdj` and `bobAdj`, for `n` nodes.
- Initialize `edges_used = 0`.
- For each Type 3 edge `(u, v)`:
    - Run a traversal (BFS/DFS) on `aliceAdj` to check if `u` and `v` are already connected.
    - If not, add the edge to both `aliceAdj` and `bobAdj`, and increment `edges_used`.
- For each Type 1 edge `(u, v)`:
    - Run a traversal on `aliceAdj` to check if `u` and `v` are connected.
    - If not, add the edge to `aliceAdj` and increment `edges_used`.
- For each Type 2 edge `(u, v)`:
    - Run a traversal on `bobAdj` to check if `u` and `v` are connected.
    - If not, add the edge to `bobAdj` and increment `edges_used`.
- Finally, run a traversal on `aliceAdj` to check if it's a single connected component.
- Do the same for `bobAdj`.
- If both are fully connected, return `total_edges - edges_used`. Otherwise, return `-1`.

## Greedy Approach with Union-Find
This approach uses a greedy strategy combined with the Union-Find (or Disjoint Set Union) data structure. The core idea is to prioritize edges that are useful for both Alice and Bob (Type 3), as they provide the most value. We build the required spanning trees for Alice and Bob by first adding all necessary Type 3 edges, and then supplementing with Type 1 edges for Alice and Type 2 edges for Bob. The Union-Find data structure is used to efficiently track the connected components and determine if adding an edge is useful (i.e., connects two previously disconnected components).
**Time:** `O(E * α(N))`, where `E` is the number of edges and `N` is the number of nodes. `α(N)` is the inverse Ackermann function, which is practically a small constant. This is because we iterate through the edges a constant number of times, and each DSU operation is amortized `O(α(N))`. · **Space:** `O(N)` to store the parent arrays for the two DSU structures.
**Pros:** Highly efficient due to the near-constant time complexity of Union-Find operations.; The greedy strategy is intuitive and correctly minimizes the number of edges required.; Simple to implement.
**Cons:** Requires understanding of the Union-Find data structure.
### Explanation
We maintain two separate Union-Find structures, one for Alice (`dsu_alice`) and one for Bob (`dsu_bob`), to track their respective graph connectivity. The algorithm proceeds in three phases:
1.  **Process Type 3 Edges:** Iterate through all Type 3 edges. For each edge `(u, v)`, attempt to union the nodes `u` and `v` in `dsu_alice`. If the union is successful (meaning `u` and `v` were in different components), it means this edge is essential for building the spanning forest. We increment our count of used edges. Since this is a Type 3 edge, it's also useful for Bob, so we perform the same union operation in `dsu_bob`.
2.  **Process Type 1 Edges:** After considering all Type 3 edges, iterate through Type 1 edges. For each edge `(u, v)`, attempt to union them only in `dsu_alice`. If the union is successful, increment the used edges count. These edges only contribute to Alice's connectivity.
3.  **Process Type 2 Edges:** Similarly, iterate through Type 2 edges. For each edge `(u, v)`, attempt to union them only in `dsu_bob`. If successful, increment the used edges count.
Finally, after processing all edges, we check if both Alice's and Bob's graphs are fully connected. A graph with `n` nodes is connected if its corresponding DSU structure has exactly one component. If both are connected, the maximum number of removable edges is the total number of initial edges minus the count of used edges. If either is not connected, it's impossible to make them both fully traversable, so we return -1.
```java
class DSU {
    private int[] parent;
    private int components;

    public DSU(int n) {
        parent = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            parent[i] = i;
        }
        components = n;
    }

    public int find(int i) {
        if (parent[i] == i) {
            return i;
        }
        return parent[i] = find(parent[i]);
    }

    public boolean union(int i, int j) {
        int rootI = find(i);
        int rootJ = find(j);
        if (rootI != rootJ) {
            parent[rootI] = rootJ;
            components--;
            return true;
        }
        return false;
    }

    public boolean isConnected() {
        return components == 1;
    }
}

class Solution {
    public int maxNumEdgesToRemove(int n, int[][] edges) {
        DSU dsuAlice = new DSU(n);
        DSU dsuBob = new DSU(n);
        int edgesUsed = 0;

        // Process Type 3 edges
        for (int[] edge : edges) {
            if (edge[0] == 3) {
                if (dsuAlice.union(edge[1], edge[2])) {
                    dsuBob.union(edge[1], edge[2]);
                    edgesUsed++;
                }
            }
        }

        // Process Type 1 edges
        for (int[] edge : edges) {
            if (edge[0] == 1) {
                if (dsuAlice.union(edge[1], edge[2])) {
                    edgesUsed++;
                }
            }
        }

        // Process Type 2 edges
        for (int[] edge : edges) {
            if (edge[0] == 2) {
                if (dsuBob.union(edge[1], edge[2])) {
                    edgesUsed++;
                }
            }
        }

        if (dsuAlice.isConnected() && dsuBob.isConnected()) {
            return edges.length - edgesUsed;
        }

        return -1;
    }
}
```
### Algorithm
- Initialize two DSU structures, `dsu_alice` and `dsu_bob`, for `n` nodes.
- Initialize `edges_used = 0`.
- Iterate through `edges` for Type 3 edges. For each `(u, v)`:
    - If `dsu_alice.union(u, v)` is successful, also perform `dsu_bob.union(u, v)` and increment `edges_used`.
- Iterate through `edges` for Type 1 edges. For each `(u, v)`:
    - If `dsu_alice.union(u, v)` is successful, increment `edges_used`.
- Iterate through `edges` for Type 2 edges. For each `(u, v)`:
    - If `dsu_bob.union(u, v)` is successful, increment `edges_used`.
- Check if both `dsu_alice` and `dsu_bob` represent connected graphs (i.e., have one component).
- If both are connected, return `total_edges - edges_used`.
- Otherwise, return `-1`.

# Solutions
### Java

```java
class UnionFind { private int [] p ; private int [] size ; public int cnt ; public UnionFind ( int n ) { p = new int [ n ]; size = new int [ n ]; for ( int i = 0 ; i < n ; ++ i ) { p [ i ] = i ; size [ i ] = 1 ; } cnt = n ; } public int find ( int x ) { if ( p [ x ] != x ) { p [ x ] = find ( p [ x ]); } return p [ x ]; } public boolean union ( int a , int b ) { int pa = find ( a - 1 ), pb = find ( b - 1 ); if ( pa == pb ) { return false ; } if ( size [ pa ] > size [ pb ]) { p [ pb ] = pa ; size [ pa ] += size [ pb ]; } else { p [ pa ] = pb ; size [ pb ] += size [ pa ]; } -- cnt ; return true ; } } class Solution { public int maxNumEdgesToRemove ( int n , int [][] edges ) { UnionFind ufa = new UnionFind ( n ); UnionFind ufb = new UnionFind ( n ); int ans = 0 ; for ( var e : edges ) { int t = e [ 0 ], u = e [ 1 ], v = e [ 2 ]; if ( t == 3 ) { if ( ufa . union ( u , v )) { ufb . union ( u , v ); } else { ++ ans ; } } } for ( var e : edges ) { int t = e [ 0 ], u = e [ 1 ], v = e [ 2 ]; if ( t == 1 && ! ufa . union ( u , v )) { ++ ans ; } if ( t == 2 && ! ufb . union ( u , v )) { ++ ans ; } } return ufa . cnt == 1 && ufb . cnt == 1 ? ans : - 1 ; } }
```

### CPP

```cpp
class UnionFind { public: int cnt ; UnionFind ( int n ) { p = vector < int > ( n ); size = vector < int > ( n , 1 ); iota ( p . begin (), p . end (), 0 ); cnt = n ; } bool unite ( int a , int b ) { int pa = find ( a - 1 ), pb = find ( b - 1 ); if ( pa == pb ) { return false ; } if ( size [ pa ] > size [ pb ]) { p [ pb ] = pa ; size [ pa ] += size [ pb ]; } else { p [ pa ] = pb ; size [ pb ] += size [ pa ]; } -- cnt ; return true ; } int find ( int x ) { if ( p [ x ] != x ) { p [ x ] = find ( p [ x ]); } return p [ x ]; } private: vector < int > p , size ; }; class Solution { public: int maxNumEdgesToRemove ( int n , vector < vector < int >>& edges ) { UnionFind ufa ( n ); UnionFind ufb ( n ); int ans = 0 ; for ( auto & e : edges ) { int t = e [ 0 ], u = e [ 1 ], v = e [ 2 ]; if ( t == 3 ) { if ( ufa . unite ( u , v )) { ufb . unite ( u , v ); } else { ++ ans ; } } } for ( auto & e : edges ) { int t = e [ 0 ], u = e [ 1 ], v = e [ 2 ]; ans += t == 1 && ! ufa . unite ( u , v ); ans += t == 2 && ! ufb . unite ( u , v ); } return ufa . cnt == 1 && ufb . cnt == 1 ? ans : - 1 ; } };
```

### Python

```python
class UnionFind : def __init__ ( self , n ): self . p = list ( range ( n )) self . size = [ 1 ] * n self . cnt = n def find ( self , x ): if self . p [ x ] != x : self . p [ x ] = self . find ( self . p [ x ]) return self . p [ x ] def union ( self , a , b ): pa , pb = self . find ( a - 1 ), self . find ( b - 1 ) if pa == pb : return False if self . size [ pa ] > self . size [ pb ]: self . p [ pb ] = pa self . size [ pa ] += self . size [ pb ] else : self . p [ pa ] = pb self . size [ pb ] += self . size [ pa ] self . cnt -= 1 return True class Solution : def maxNumEdgesToRemove ( self , n : int , edges : List [ List [ int ]]) -> int : ufa = UnionFind ( n ) ufb = UnionFind ( n ) ans = 0 for t , u , v in edges : if t == 3 : if ufa . union ( u , v ): ufb . union ( u , v ) else : ans += 1 for t , u , v in edges : if t == 1 : ans += not ufa . union ( u , v ) if t == 2 : ans += not ufb . union ( u , v ) return ans if ufa . cnt == 1 and ufb . cnt == 1 else - 1
```