NeetCode #648LC-1579HardAdvanced Graphs
← Back to All Problems#648 · #1579 · Remove Max Number of Edges to Keep Graph Fully Traversable(保证图可完全遍历)
📌 Problem Statement & Constraints
Alice and Bob share an undirected graph of
n nodes. edges[i] = [type, u, v]: type 1 is Alice-only, type 2 is Bob-only, type 3 is both. Return the maximum number of edges that can be removed while keeping the graph fully traversable for both, or -1. Constraints: 1 <= n <= 10^5, 1 <= edges.length <= min(10^5, 3 * n * (n - 1) / 2).💡 Core Algorithmic Approaches
- Run two independent union-finds, one per person.
- Greedy order matters: use type-3 edges first (they help both), then type-1 for Alice and type-2 for Bob.
- Count the edges actually used; the answer is
total - used. - If either union-find does not end with a single component, return -1.
💻 Benchmark Python3 Implementation
class Solution:
def maxNumEdgesToRemove(self, n: int, edges: List[List[int]]) -> int:
parent_a = list(range(n + 1))
parent_b = list(range(n + 1))
def find(parent: list, x: int) -> int:
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
used = 0
# 1) type-3 edges first: they serve both people
for t, u, v in edges:
if t != 3:
continue
ra, rb = find(parent_a, u), find(parent_a, v)
ra2, rb2 = find(parent_b, u), find(parent_b, v)
if ra != rb or ra2 != rb2:
used += 1 # this edge is necessary for someone
if ra != rb:
parent_a[ra] = rb
if ra2 != rb2:
parent_b[ra2] = rb2
# 2) type-1 for Alice, type-2 for Bob
for t, u, v in edges:
if t == 1:
ra, rb = find(parent_a, u), find(parent_a, v)
if ra != rb:
used += 1
parent_a[ra] = rb
elif t == 2:
ra, rb = find(parent_b, u), find(parent_b, v)
if ra != rb:
used += 1
parent_b[ra] = rb
# 3) both must be able to traverse everything
if len({find(parent_a, i) for i in range(1, n + 1)}) != 1:
return -1
if len({find(parent_b, i) for i in range(1, n + 1)}) != 1:
return -1
return len(edges) - used⚡ Complexity Deep Dive
⏱️ Time Complexity
O(E * alpha): two passes over the edges.
💾 Space Complexity
O(n) for the two union-finds.
⚠️ Interview Pitfalls & Follow-ups
- Processing type-1 and type-2 before type-3: shared edges would be wasted.
- Counting an edge as used only when it merges both unions: it counts if it merges either.
- Forgetting the connectivity check: the answer is -1 if either person cannot reach everything.
- Using a single union-find: the two people have different edge sets.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.