Scale Engineer

Remove Max Number of Edges to Keep Graph Fully Traversable

Hard
#1453Time: `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.
Algorithms
Union Find
Data structures
Graph

Prompt

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:

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 <= 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

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.
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;    }}

Complexity

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.

Trade-offs

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.

Solutions

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 ; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem