⚡Flashcard Drill➔
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

  1. Run two independent union-finds, one per person.
  2. Greedy order matters: use type-3 edges first (they help both), then type-1 for Alice and type-2 for Bob.
  3. Count the edges actually used; the answer is total - used.
  4. 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.
🎯 Drill This Card Now➔

🧩 Related Advanced Graphs Problems