1579. Remove Max Number of Edges to Keep Graph Fully Traversable

1579

HardUnion-Find / Disjoint Set UnionUnion-Find (two disjoint-set structures)Dual Union-Find, prioritize shared edges

Remove Max Number of Edges to Keep Graph Fully Traversable

An undirected graph on n nodes (labeled 1..n) has three edge types: type 1 usable only by Alice, type 2 usable only by Bob, and type 3 usable by both. edges[i] = [type, u, v]. Remove as many edges as possible while the graph remains fully traversable -- meaning Alice alone can reach every node from every node, and Bob alone can too. Return the maximum number of removable edges, or -1 if the graph cannot be made fully traversable by both.

Open official problem prompt ↗

In plain English

Keep the smallest set of edges that still lets both Alice and Bob independently reach every node, and report how many edges that lets us throw away.

Picture it like this

Two delivery companies share some roads and each owns private roads. To keep both able to reach every town, first pave the shared roads (they count double), then patch each company's remaining gaps with its private roads. Any road not needed to connect a new town can be torn up.

Example

Input: n = 4, edges = [[3,1,2],[3,2,3],[1,1,3],[1,2,4],[1,1,2],[2,3,4]]
Output: 2
Why: Keeping both type-3 edges plus Alice's [2,4] and Bob's [3,4] connects everything for both; the remaining 2 edges ([1,1,3] and [1,1,2]) are redundant and removable.

Constraints

1 <= n <= 10^51 <= edges.length <= min(10^5, 3 * n * (n-1) / 2)edges[i].length == 31 <= edges[i][0] <= 31 <= u_i < v_i <= nAll tuples (type_i, u_i, v_i) are distinct

Pattern lesson

See the pattern, then code

Dual Union-Find, prioritize shared edges

↗

Union-Find / Disjoint Set Union

Dynamic connectivity, merging groups, redundant edges, or Kruskal's algorithm.. An edge is worth keeping only if it merges two currently separate components for someone. Type-3 edges help both agents, so add them first to maximize sharing; then fill each agent's remaining gaps with their exclusive edges. Every edge that never merges anything is removable.

New words, made simpleKnow these before the algorithm

Fully traversable: A single agent can travel between any pair of nodes using only edges available to that agent
Shared (type-3) edge: An edge usable by both agents; keeping it benefits both connectivity structures at once
Spanning tree: A minimal set of n-1 edges that keeps n nodes connected; the goal is one such tree per agent, sharing as much as possible
Used edge: An edge whose union merged two previously separate components -- it earns its place in the kept set

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Brute-force edge subset testing

Exponential and hopelessly slow for up to 10^5 edges.

Try removing subsets of edges and check that both agents stay fully connected

Time O(2^E * E)Space O(n + E)

Best choiceGreedy dual Union-Find, type-3 first

Near-linear and provably optimal: prioritizing shared edges minimizes total kept edges.

Add type-3 edges to both DSUs first, then each agent's exclusive edges; keep only edges that merge components and verify both reach a single component

Time O(E * alpha(n))Space O(n)

The rule we keep true

Invariant

At any moment, each DSU's kept edges form a forest (no cycles), and its component counter equals the number of separate groups that agent can still not bridge; a single component means that agent is fully traversable.

Why this is correct

Reasoning

Each agent needs a spanning tree of n-1 edges. A type-3 edge that merges components counts toward both trees simultaneously, so using type-3 edges before exclusive ones never wastes an opportunity and can only reduce the total kept. Any edge whose endpoints are already connected for its owner adds a cycle and is safely removable. If after using every helpful edge an agent still has more than one component, that agent cannot be made fully traversable and the answer is -1.

The algorithm in three movesSay these aloud before coding

1Build two DSUs, one for Alice and one for Bob, each with n nodes

type-3: [1,2],[2,3] used by both -> 2 used

2Process type-3 edges first: union in both DSUs; count the edge as used if it merged anything

Alice fills [2,4]; Bob fills [3,4] -> 2 more used

3Process type-1 edges in Alice's DSU and type-2 edges in Bob's DSU, counting used merges

both DSUs 1 component; removable = 6 - 4 = 2

4If either DSU is not reduced to a single component, return -1; otherwise return total edges minus used edges

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Read[3,1,2]

2 · AskMerge in both DSUs?

3 · Update stateAlice 4->3 comps, Bob 4->3

4 · ResultUsed (both merged)

Key takeaway

All four nodes end fully connected for both agents using 4 kept edges out of 6.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 3-21Reusable DSU class
1-indexed parent array (size n+1) with path compression; union returns True only when it actually merges two roots, and count tracks remaining components.
2
Lines 23-24Two independent structures
Alice and Bob get separate DSUs so their connectivity is tracked independently while sharing the same node labels.
3
Lines 25-31Shared edges first
Type-3 edges are added to both DSUs before any exclusive edge; counted as used if they merged something for either agent (they merge for both or neither here).
4
Lines 32-38Fill exclusive gaps
Type-1 edges patch Alice's remaining components, type-2 patch Bob's; only merging edges are counted as used.
5
Lines 39-41Feasibility and result
Both DSUs must collapse to one component; if so the removable count is total edges minus the kept (used) edges, else the graph cannot be fully traversable so return -1.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

A node reachable by no edge for one agent: that agent stays multi-component, return -1
Only type-3 edges given and they span the graph: both agents share one tree, maximal removals
Duplicate-purpose edges (extra type-1 after Alice is connected): all removable
n = 1: zero components to merge, every edge is removable and both are trivially traversable

Common beginner mistakes

Processing type-1 or type-2 edges before type-3, which can waste exclusive edges and undercount removals
Double-counting a type-3 edge as two used edges instead of one
Sizing the parent array to n instead of n+1 and mishandling the 1-based node labels
Forgetting to check BOTH DSUs reach a single component before returning a non-negative answer

Check your understanding

Why must type-3 edges be added before the exclusive type-1 and type-2 edges rather than after?

PyPython 3 · solution.py

Optimal

1class Solution:2    def maxNumEdgesToRemove(self, n: int, edges: List[List[int]]) -> int:3        class DSU:4            def __init__(self, n: int):5                self.parent = list(range(n + 1))6                self.count = n78            def find(self, x: int) -> int:9                while self.parent[x] != x:10                    self.parent[x] = self.parent[self.parent[x]]11                    x = self.parent[x]12                return x1314            def union(self, a: int, b: int) -> bool:15                ra, rb = self.find(a), self.find(b)16                if ra == rb:17                    return False18                self.parent[ra] = rb19                self.count -= 120                return True2122        alice, bob = DSU(n), DSU(n)23        used = 024        for t, u, v in edges:25            if t == 3:26                a = alice.union(u, v)27                b = bob.union(u, v)28                if a or b:29                    used += 130        for t, u, v in edges:31            if t == 1:32                if alice.union(u, v):33                    used += 134            elif t == 2:35                if bob.union(u, v):36                    used += 137        if alice.count == 1 and bob.count == 1:38            return len(edges) - used39        return -1

Time complexityO(E * alpha(n))Optimized

Space complexityO(n)Explained

Interview rehearsal

Explain before you code

25:00

Restate constraints and edge cases
Explain brute force and its bottleneck
State the invariant and complexity

Seen at

GoogleAmazonMeta

Remove Max Number of Edges to Keep Graph Fully Traversable

Remove Max Number of Edges to Keep Graph Fully Traversable

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Union-Find / Disjoint Set Union