Remove Max Number of Edges to Keep Graph Fully Traversable hard
Description
Alice and Bob have an undirected graph of n nodes and three types of edges:
- Type 1: Can be traversed by Alice only.
- Type 2: Can be traversed by Bob only.
- Type 3: Can be traversed by both Alice and Bob.
Given an array edges where edges[i] = [typei, ui, vi] represents a bidirectional edge of type typei between nodes ui and vi, find the maximum number of edges you can remove so that after the removal, the graph can still be fully traversed by both Alice and Bob.
Return the maximum number of edges removed, or return -1 if the graph cannot be fully traversed by both.
Examples
> Case 1:
n = 4, edges = [[3,1,2],[3,2,3],[1,1,3],[1,2,4],[1,1,2],[2,3,4]]
Output: 2
> Case 2:
n = 4, edges = [[3,1,2],[3,2,3],[1,1,4],[2,1,4]]
Output: 0
> Case 3:
n = 4, edges = [[3,1,2],[3,2,3],[1,2,3],[2,2,3]]
Output: -1Constraints
1 <= n <= 10^51 <= edges.length <= min(10^5, 3 × n × (n-1) / 2)edges[i].length == 31 <= typei <= 31 <= ui < vi <= n
State design / Intuition
Minimize edges kept = maximize edges removed.
To keep the graph fully traversable for both Alice and Bob, we need Alice’s edges (type 1 + type 3) to form a spanning tree, and Bob’s edges (type 2 + type 3) to form a spanning tree.
Key insight: Use two separate Union-Find structures — one for Alice, one for Bob. Process type 3 edges first (shared edges) because they’re more valuable — a type 3 edge counts toward both spanning trees simultaneously.
Algorithm:
- Process all type 3 edges first: add to both Alice’s and Bob’s union-find. An edge is useful if it connects two previously disconnected components in at least one of them. If it doesn’t help either, remove it.
- Process type 1 edges (Alice only): add to Alice’s union-find. If redundant, remove.
- Process type 2 edges (Bob only): add to Bob’s union-find. If redundant, remove.
- Check both union-finds have exactly 1 component. If not, return -1.
Code
Why process type 3 edges first? A type 3 edge can help Alice and Bob simultaneously. If we process type 1/2 edges first and “use up” connectivity slots, we might later process a type 3 edge that only helps one of them — forcing us to keep an extra edge. Processing shared edges first maximizes their dual contribution and minimizes the total kept.
Analysis
- Time: O(E α(V)) ≈ O(E).
- Space: O(V) for two union-find structures.
Same skin
- Redundant Connection — single union-find version.
- Find Critical Edges — vary which edges are forced or skipped.
- Optimize Water Distribution — single union-find with a virtual node.
- Satisfiability of Equality Equations — union-find with type-based edge processing.