Remove Max Number of Edges to Keep Graph Fully Traversable — Hard Problem & Solution

Problem statement

Alice and Bob share an undirected graph of n nodes numbered 1 to n. Each edges[i] = [typei, ui, vi] is an edge between ui and vi of one of three types:

• type 1: only Alice can use it,
• type 2: only Bob can use it,
• type 3: both can use it.

The graph is fully traversable for a person if, using only the edges they may use, they can get from any node to any other node.

Return the maximum number of edges you can remove so that the graph stays fully traversable for both Alice and Bob, or -1 if it is not fully traversable for both to begin with.

Example 1

Input: n = 3, edges = [[3,1,2],[1,2,3],[2,2,3],[1,1,3],[3,2,3]]
Output: 3
Explanation: The two shared edges `[3,1,2]` and `[3,2,3]` already connect everything for both; the other three can go.

Example 2

Input: n = 4, edges = [[3,1,2],[1,2,3],[2,3,4],[1,3,4],[2,2,3]]
Output: 0

Example 3

Input: n = 3, edges = [[1,1,2],[2,2,3],[3,1,2]]
Output: -1
Explanation: Alice can never reach node 3.

Constraints

• 1 <= n <= 10^5
• 1 <= edges.length <= min(10^5, 3 * n * (n - 1) / 2)
• edges[i].length == 3
• 1 <= typei <= 3
• 1 <= ui < vi <= n
• all tuples (typei, ui, vi) are distinct

How to solve Remove Max Number of Edges to Keep Graph Fully Traversable

Greedy union-find: take shared edges first (each can serve both people), then private edges only where still needed; every edge that merges nothing is removable.

Approach

1. Create union-finds for Alice and Bob over nodes 1..n.
2. For each type-3 edge, union it in both structures if it merges two of Alice's sets (Bob's structure is identical at this point); count it as kept.
3. For each type-1 edge, union it in Alice's structure, counting it if it merges; likewise type-2 edges in Bob's structure.
4. If either structure has more than one component, return -1; otherwise return edges.length − kept.

Why it works

Each person needs a spanning forest of exactly n − 1 edges. Let s be the number of shared edges used; then the kept total is s + (n − 1 − s) + (n − 1 − s) = 2(n − 1) − s, so maximising s is the whole game. Adding all useful type-3 edges first yields a spanning forest of the type-3 subgraph, which has the maximum possible number of shared edges; the private edges then complete each person's tree independently, using the minimum number for each.

Complexity

• Time — O(m · α(n))
• Space — O(n)

Pitfalls

• Processing edges in input order instead of type 3 first can waste private edges where a shared edge would have done.
• A type-3 edge that merges nothing for Alice also merges nothing for Bob — they share the same history at that stage.
• Check both people's connectivity at the end; either one failing means -1.

Reference solution

Python

from typing import List

def maxNumEdgesToRemove(n: int, edges: List[List[int]]) -> int:
    alice = list(range(n + 1))
    bob = list(range(n + 1))

    def find(root, x):
        while root[x] != x:
            root[x] = root[root[x]]
            x = root[x]
        return x

    def union(root, a, b):
        ra, rb = find(root, a), find(root, b)
        if ra == rb:
            return False
        root[ra] = rb
        return True

    used = 0
    comps_a = comps_b = n
    for t, u, v in edges:
        if t == 3 and union(alice, u, v):
            union(bob, u, v)
            used += 1
            comps_a -= 1
            comps_b -= 1
    for t, u, v in edges:
        if t == 1 and union(alice, u, v):
            used += 1
            comps_a -= 1
        elif t == 2 and union(bob, u, v):
            used += 1
            comps_b -= 1
    if comps_a != 1 or comps_b != 1:
        return -1
    return len(edges) - used

JavaScript

var maxNumEdgesToRemove = function(n, edges) {
    var alice = [], bob = [];
    for (var i = 0; i <= n; i++) { alice.push(i); bob.push(i); }
    var find = function(root, x) {
        while (root[x] !== x) { root[x] = root[root[x]]; x = root[x]; }
        return x;
    };
    var union = function(root, a, b) {
        var ra = find(root, a), rb = find(root, b);
        if (ra === rb) return false;
        root[ra] = rb;
        return true;
    };
    var used = 0, compsA = n, compsB = n;
    for (var k = 0; k < edges.length; k++) {
        var e = edges[k];
        if (e[0] === 3 && union(alice, e[1], e[2])) { union(bob, e[1], e[2]); used++; compsA--; compsB--; }
    }
    for (var j = 0; j < edges.length; j++) {
        var f = edges[j];
        if (f[0] === 1 && union(alice, f[1], f[2])) { used++; compsA--; }
        else if (f[0] === 2 && union(bob, f[1], f[2])) { used++; compsB--; }
    }
    if (compsA !== 1 || compsB !== 1) return -1;
    return edges.length - used;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More greedy problems

• Minimum Cost to Make at Least One Valid Path in a Grid Hard
• Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree Hard
• Minimize Malware Spread Hard
• Sum of Distances in Tree Hard
• Shortest Cycle in a Graph Hard
• Divide Nodes Into the Maximum Number of Groups Hard