hard

Remove Max Number of Edges to Keep Graph Fully Traversable

Find the maximum number of edges removable while keeping a graph traversable by two travelers.

1. Define the problem

Remove Max Number of Edges to Keep Graph Fully Traversable

Alice and Bob need to traverse a graph of n nodes fully — reach any node from any other. Edges come in three types: type 1 (Alice only), type 2 (Bob only), and type 3 (both). Given edges where edgesi = [typei, ui, vi], return the maximum number of edges that can be removed while both Alice and Bob can still fully traverse the graph, or -1 if it is impossible for both. Process shared edges first , unioning them into two separate union-find structures — one for Alice, one for Bob. Then union the remaining type-1 edges into Alice’s structure only and type-2 edges into Bob’s structure only . Every edge that actually merges two groups is required; every other edge can be removed.

Constraints

  • 1 ≤ n ≤ 105
  • 1 ≤ edges.length ≤ min(105, 3 * n * (n - 1) / 2)
  • edgesi.length == 3
  • 1 ≤ typei ≤ 3
  • 1 ≤ ui < vi ≤ n
  • All tuples (typei, ui, vi) are distinct

Example

Inputn = 4, edges = [[3,1,2],[3,2,3],[1,1,3],[1,2,4],[1,1,2],[2,3,4]]
Output2

Explanation Using both type-3 edges plus one type-1 edge connects Alice; using both type-3 edges plus the type-2 edge connects Bob. 4 of the 6 edges are needed, so 2 can be removed.

2. Know the words first

In plain terms

Fully traversable
Every node can be reached from every other node using only that person’s allowed edges.
3. Visualize the solution

Shared edges first, then each person’s private edges — count what is actually needed

Shared edges first, then each person’s private edges — count what is actually needed
Statusused: 0

Shared edge 1–2: separate groups for both Alice and Bob — union in both, needed. used: 1.

What happens in this step

edge (1,2), type 3 (shared)
find_Alice(1)=1, find_Alice(2)=2 → different → union, needed
find_Bob(1)=1, find_Bob(2)=2 → different → union, needed

used=1. Alice: {1,2}, Bob: {1,2}
Step 1 of 5

Steps to visualize

  1. Union every type-3 (shared) edge into both Alice’s and Bob’s union-find structures.
  2. Union every remaining type-1 edge into Alice’s structure only.
  3. Union every remaining type-2 edge into Bob’s structure only.
  4. If either structure ends with more than one group, return -1 — full traversal is impossible.
  5. Otherwise, the answer is the total edge count minus every edge that actually merged two groups.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Shared edges first, then each person’s private edges — count what is actually needed
Statusused: 0

Shared edge 1–2: separate groups for both Alice and Bob — union in both, needed. used: 1.

What happens in this step

edge (1,2), type 3 (shared)
find_Alice(1)=1, find_Alice(2)=2 → different → union, needed
find_Bob(1)=1, find_Bob(2)=2 → different → union, needed

used=1. Alice: {1,2}, Bob: {1,2}
Step 1 of 5
5. Solution

Solution

solution.tsTypeScript
function maxNumEdgesToRemove(n, edges) {
  function makeUnionFind(size) {
    const parent = Array.from({ length: size + 1 }, (_, i) => i);

    function find(x) {
      while (parent[x] !== x) {
        parent[x] = parent[parent[x]];
        x = parent[x];
      }
      return x;
    }

    function union(a, b) {
      const rootA = find(a);
      const rootB = find(b);
      if (rootA === rootB) return false;
      parent[rootA] = rootB;
      return true;
    }

    function componentCount() {
      let count = 0;
      for (let i = 1; i <= size; i++) {
        if (find(i) === i) count++;
      }
      return count;
    }

    return { union, componentCount };
  }

  const ufAlice = makeUnionFind(n);
  const ufBob = makeUnionFind(n);
  let usedEdges = 0;

  for (const [type, a, b] of edges) {
    if (type === 3) {
      const neededByAlice = ufAlice.union(a, b);
      ufBob.union(a, b);
      if (neededByAlice) usedEdges++;
    }
  }

  for (const [type, a, b] of edges) {
    if (type === 1) {
      if (ufAlice.union(a, b)) usedEdges++;
    } else if (type === 2) {
      if (ufBob.union(a, b)) usedEdges++;
    }
  }

  if (ufAlice.componentCount() !== 1 || ufBob.componentCount() !== 1) {
    return -1;
  }

  return edges.length - usedEdges;
}
Time
O((n + m) · α(n))
Space
O(n)
6. Test cases

Test cases

InputExpectedCovers
n = 4, edges = [[3,1,2],[3,2,3],[1,1,3],[1,2,4],[1,1,2],[2,3,4]]2example from the docstring
n = 4, edges = [[3,1,2],[3,2,3],[1,1,4],[2,1,4]]0exactly enough edges for both, nothing spare
n = 4, edges = [[3,2,3],[1,1,2],[2,3,4]]-1Alice can never reach node 4 with these edges — impossible
n = 2, edges = [[3,1,2]]0smallest valid input, one shared edge connects both
n = 2, edges = [[1,1,2],[2,1,2]]0no type-3 edge exists — each person needs their own private edge
n = 3, edges = [[1,1,2],[1,2,3]]-1Bob has no usable edges at all, so he can never fully traverse

Keep reading