Problem 27.5 · Minimum Spanning TreesHard

Remove Max Number of Edges to Keep Graph Fully Traversable

PatternUnion-Find Minimum Spanning Tree Greedy Choice

What it teaches: Two spanning structures sharing edges: take shared edges first, then each person's own.

Practise it on judges as “Remove Max Number of Edges to Keep Graph Fully Traversable”.

The problem

Edges have type 1 (Alice only), 2 (Bob only) or 3 (both). Return the maximum number of edges you can remove so both Alice and Bob can still reach every node 1..n, or −1 if they can't even now.

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

Constraints

1 ≤ n ≤ 10⁵

Pattern clues in the wording

→ Two users, shared and private edges
→ Keep the minimum to stay connected

These clues point to Union-Find: Keep each group as a tree with a root; find the root to test membership and link roots to merge groups.

Stuck? Take one hint at a time

Solution.java · starter

class Solution {
    public int maxNumEdgesToRemove(int n, int[][] edges) {
        return -1;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	n = 4 edges = [[3,1,2],[3,2,3],[1,1,3],[1,2,4],[1,1,2],[2,3,4]]	2
2	n = 4 edges = [[3,1,2],[3,2,3],[1,1,4],[2,1,4]]	0
3	n = 4 edges = [[3,2,3],[1,1,2],[2,3,4]]	-1

From slow to fast

Approaches

1. Two DSUs, shared edges first · O(E α(n))

Two DSUs, shared edges first

Time O(E α(n)) Space O(n)

Process type 3 edges into both DSUs (count once if useful), then type 1 into Alice's, type 2 into Bob's. If either isn't connected, −1. Otherwise answer = edges − used.

Approach 1

class Solution {
    public int maxNumEdgesToRemove(int n, int[][] edges) {
        int[] alice = new int[n + 1], bob = new int[n + 1];
        for (int i = 0; i <= n; i++) { alice[i] = i; bob[i] = i; }
        int used = 0, aliceParts = n, bobParts = n;
        for (int[] e : edges)
            if (e[0] == 3 && union(alice, e[1], e[2])) {
                union(bob, e[1], e[2]);
                used++; aliceParts--; bobParts--;
            }
        for (int[] e : edges) {
            if (e[0] == 1 && union(alice, e[1], e[2])) { used++; aliceParts--; }
            if (e[0] == 2 && union(bob, e[1], e[2])) { used++; bobParts--; }
        }
        return aliceParts == 1 && bobParts == 1 ? edges.length - used : -1;
    }

    private boolean union(int[] parent, int a, int b) {
        int ra = find(parent, a), rb = find(parent, b);
        if (ra == rb) return false;
        parent[ra] = rb;
        return true;
    }

    private int find(int[] parent, int x) {
        while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; }
        return x;
    }
}

Verdict: Greedy order is the key.

Before you submit

Edge cases and common mistakes

Test these inputs

Only type-3 edges
One person disconnected (−1)

Mistakes people make

Processing private edges before shared ones (uses more edges than needed).

Interview

Follow-up questions

Why are shared edges first always safe?

Command Palette

The problem

Approaches

Two DSUs, shared edges first

Edge cases and common mistakes

Follow-up questions