Stage 4: Advanced Techniques·Advanced Graph

Hard#15798 min readGraphUnion-FindLeetCode

Remove Max Edges to Keep Graph Traversable

Union-Find with type-3 priority

Dual Union-Find. Process shared edges first (greedy).

Published Apr 16, 2026

Problem

Alice and Bob share an undirected graph of n nodes. There are three edge types:

Type 1 — usable by Alice only.
Type 2 — usable by Bob only.
Type 3 — usable by both.

Return the maximum number of edges you can remove so that both Alice and Bob can still independently traverse the entire graph. If the graph cannot be made fully traversable by both, return -1.

Input

n = 4, edges = [[3,1,2],[3,2,3],[1,1,3],[1,2,4],[1,1,2],[2,3,4]]

Output

Explanation

Remove edges [1,1,2] and [1,2,4]. Alice connects via type-3 + type-1 edges (1-2, 2-3, 1-3). Bob via type-3 + type-2 edges.

Input

n = 4, edges = [[3,1,2],[3,2,3],[1,1,4],[2,1,4]]

Output

Explanation

All four edges are needed. Removing any one disconnects either Alice or Bob.

Input

n = 4, edges = [[3,2,3],[1,1,2],[2,3,4]]

Output

-1

Explanation

Bob cannot reach all nodes — no type-2 or type-3 path connects node 1 to node 2.

Intuition

Maximize removals = minimize kept edges. An n-node connected graph needs at least n - 1 edges (a spanning tree). Alice needs her own spanning tree (type 1 + type 3) and Bob needs his (type 2 + type 3).

The trick: type-3 edges count for both trees simultaneously. Every type-3 edge used saves us from needing one type-1 and one type-2 edge. So greedily prefer type-3 edges.

Algorithm:

Process all type-3 edges first with a shared union-find. Each successful union means one fewer edge needed in both Alice's and Bob's trees.
Copy the union-find state into Alice's and Bob's separate DSUs.
Process type-1 edges on Alice's DSU, type-2 on Bob's. Count how many unions succeed (each is a kept edge).
If either DSU is not fully connected, return -1.
Otherwise, return total_edges - kept_edges.

Approach

Brute Force

TimeO(2^E · E · α(V))

SpaceO(V)

Try all subsets of edges (exponential) and check connectivity for both. Not practical, but establishes correctness baseline.

impl Solution {
    pub fn max_num_edges_to_remove(n: i32, edges: Vec<Vec<i32>>) -> i32 {
        let n = n as usize;
        let m = edges.len();

        // Try removing as many edges as possible by checking all
        // 2^m subsets (only feasible for small m).
        let mut best = -1i32;
        'outer: for mask in 0..(1u64 << m) {
            let mut pa: Vec<usize> = (0..=n).collect();
            let mut pb: Vec<usize> = (0..=n).collect();
            fn find(p: &mut [usize], mut x: usize) -> usize {
                while p[x] != x { p[x] = p[p[x]]; x = p[x]; }
                x
            }
            fn union(p: &mut [usize], a: usize, b: usize) -> bool {
                let (ra, rb) = (find(p, a), find(p, b));
                if ra == rb { return false; }
                p[ra] = rb; true
            }
            for j in 0..m {
                if mask & (1u64 << j) == 0 { continue; }
                let (t, u, v) = (edges[j][0], edges[j][1] as usize, edges[j][2] as usize);
                if t == 1 || t == 3 { union(&mut pa, u, v); }
                if t == 2 || t == 3 { union(&mut pb, u, v); }
            }
            let ca = (1..=n).map(|i| find(&mut pa, i)).collect::<std::collections::HashSet<_>>().len();
            let cb = (1..=n).map(|i| find(&mut pb, i)).collect::<std::collections::HashSet<_>>().len();
            if ca == 1 && cb == 1 {
                let kept = (0..m).filter(|&j| mask & (1u64 << j) != 0).count() as i32;
                let removed = m as i32 - kept;
                if removed > best { best = removed; }
            }
        }
        best
    }
}

Rust · runnable

function maxNumEdgesToRemove(n: number, edges: number[][]): number {
  // Brute force: try all subsets (only for small m).
  const m = edges.length;
  let best = -1;
  for (let mask = 0; mask < (1 << m); mask++) {
    const pa = Array.from({ length: n + 1 }, (_, i) => i);
    const pb = Array.from({ length: n + 1 }, (_, i) => i);
    const find = (p: number[], x: number): number => {
      while (p[x] !== x) { p[x] = p[p[x]]; x = p[x]; }
      return x;
    };
    const union = (p: number[], a: number, b: number): boolean => {
      const ra = find(p, a), rb = find(p, b);
      if (ra === rb) return false;
      p[ra] = rb; return true;
    };
    for (let j = 0; j < m; j++) {
      if (!(mask & (1 << j))) continue;
      const [t, u, v] = edges[j];
      if (t === 1 || t === 3) union(pa, u, v);
      if (t === 2 || t === 3) union(pb, u, v);
    }
    const ca = new Set(Array.from({ length: n }, (_, i) => find(pa, i + 1))).size;
    const cb = new Set(Array.from({ length: n }, (_, i) => find(pb, i + 1))).size;
    if (ca === 1 && cb === 1) {
      const kept = m - [...Array(m).keys()].filter(j => !(mask & (1 << j))).length;
      const removed = m - kept;
      if (removed > best) best = removed;
    }
  }
  return best;
}

TypeScript · runnable

Union-Find with Type-3 Priority

TimeO(E · α(V))

SpaceO(V)

Recommended

Process type-3 edges on a shared DSU first. Then branch into Alice-only and Bob-only DSUs. Count total unions.

impl Solution {
    pub fn max_num_edges_to_remove(n: i32, edges: Vec<Vec<i32>>) -> i32 {
        let n = n as usize;
        let m = edges.len();

        let mut pa: Vec<usize> = (0..=n).collect();
        let mut ra = vec![0usize; n + 1];
        let mut ca = n;

        fn find(p: &mut [usize], mut x: usize) -> usize {
            while p[x] != x { p[x] = p[p[x]]; x = p[x]; }
            x
        }
        fn union(p: &mut [usize], r: &mut [usize], c: &mut usize, a: usize, b: usize) -> bool {
            let (ra2, rb2) = (find(p, a), find(p, b));
            if ra2 == rb2 { return false; }
            if r[ra2] < r[rb2] { p[ra2]= rb2; }
            else if r[ra2] > r[rb2] { p[rb2] = ra2; }
            else { p[rb2] = ra2; r[ra2] += 1; }
            *c -= 1;
            true
        }

        let mut kept = 0;

        // Phase 1: type-3 edges (shared).
        for e in &edges {
            if e[0] == 3 {
                if union(&mut pa, &mut ra, &mut ca, e[1] as usize, e[2] as usize) {
                    kept += 1;
                }
            }
        }

        // Copy state for Bob.
        let mut pb = pa.clone();
        let mut rb = ra.clone();
        let mut cb = ca;

        // Phase 2: type-1 (Alice only).
        for e in &edges {
            if e[0] == 1 {
                if union(&mut pa, &mut ra, &mut ca, e[1] as usize, e[2] as usize) {
                    kept += 1;
                }
            }
        }

        // Phase 3: type-2 (Bob only).
        for e in &edges {
            if e[0] == 2 {
                if union(&mut pb, &mut rb, &mut cb, e[1] as usize, e[2] as usize) {
                    kept += 1;
                }
            }
        }

        if ca != 1 || cb != 1 {
            return -1;
        }

        (m as i32) - kept
    }
}

Rust · runnable

function maxNumEdgesToRemove(n: number, edges: number[][]): number {
  const m = edges.length;

  const makeUF = (size: number) => {
    const parent = Array.from({ length: size + 1 }, (_, i) => i);
    const rank = new Array(size + 1).fill(0);
    let components = size;
    const find = (x: number): number => {
      while (parent[x] !== x) { parent[x] = parent[parent[x]]; x = parent[x]; }
      return x;
    };
    const union = (a: number, b: number): boolean => {
      const ra = find(a), rb = find(b);
      if (ra === rb) return false;
      if (rank[ra] < rank[rb]) parent[ra] = rb;
      else if (rank[ra] > rank[rb]) parent[rb] = ra;
      else { parent[rb] = ra; rank[ra]++; }
      components--;
      return true;
    };
    return { parent, rank, components: () => components, find, union };
  };

  const shared = makeUF(n);
  let kept = 0;

  // Phase 1: type-3 edges.
  for (const [t, u, v] of edges) {
    if (t === 3 && shared.union(u, v)) kept++;
  }

  // Clone shared state for Alice and Bob.
  const alice = makeUF(n);
  const bob = makeUF(n);
  // Overwrite with shared state.
  for (let i = 0; i <= n; i++) {
    alice.parent[i] = shared.parent[i];
    alice.rank[i] = shared.rank[i];
    bob.parent[i] = shared.parent[i];
    bob.rank[i] = shared.rank[i];
  }
  // Hack: manually set components.
  let aliceComp = shared.components();
  let bobComp = shared.components();

  // Phase 2: type-1 (Alice).
  for (const [t, u, v] of edges) {
    if (t === 1) {
      const ra = alice.find(u), rb = alice.find(v);
      if (ra !== rb) {
        alice.union(u, v);
        aliceComp--;
        kept++;
      }
    }
  }

  // Phase 3: type-2 (Bob).
  for (const [t, u, v] of edges) {
    if (t === 2) {
      const ra = bob.find(u), rb = bob.find(v);
      if (ra !== rb) {
        bob.union(u, v);
        bobComp--;
        kept++;
      }
    }
  }

  if (aliceComp !== 1 || bobComp !== 1) return -1;
  return m - kept;
}

TypeScript · runnable

Trace

n = 4, edges = [[3,1,2],[3,2,3],[1,1,3],[1,2,4],[1,1,2],[2,3,4]]:

phase	edge	type	action	kept
shared	(1,2)	3	union	1
shared	(2,3)	3	union	2
alice	(1,3)	1	cycle (1,3 already connected)	2
alice	(2,4)	1	union	3
alice	(1,2)	1	cycle	3
bob	(3,4)	2	union	4

After all phases: Alice has 1 component, Bob has 1 component. Kept = 4, total = 6, removed = 2.

Edge cases

All type-3 — one shared tree spans both. Remove m - (n - 1) edges.
No type-3 — Alice and Bob need independent spanning trees. Each needs n - 1 edges.
Disconnected even with all edges — return -1.
Parallel edges — the union-find naturally deduplicates; extra edges contribute to "removed".

Takeaway

Shared resources go first. The type-3-priority greedy is optimal because a shared edge is strictly more valuable (saves from both personal budgets). This greedy logic extends to real multi-tenant resource provisioning — shared infrastructure beats per-user infrastructure when capacity allows.

Hard#1489

Find Critical and Pseudo-Critical Edges in MST

Kruskal’s + edge classification. Deep graph understanding.

Hard#1192

Critical Connections in a Network

Tarjan’s bridge-finding algorithm. Must-know for systems interviews.

More in Advanced Graph

Medium#787

Cheapest Flights Within K Stops

Bellman-Ford with K rounds. You already know this from your arb bot.

Hard#1192

Critical Connections in a Network

Tarjan’s bridge-finding algorithm. Must-know for systems interviews.

Hard#1489

Find Critical and Pseudo-Critical Edges in MST

Kruskal’s + edge classification. Deep graph understanding.

View #1579 on LeetCode