Remove Max Number of Edges to Keep Graph Fully Traversable

You are given an undirected graph of n nodes and an array of edges where each edge is [type, u, v]. Type 1 edges can only be traversed by Alice, type 2 only by Bob, and type 3 by both. Return the maximum number of edges you can remove so that the graph remains fully traversable by both Alice and Bob. If the graph cannot be made fully traversable by both, return -1.

This is LeetCode 1579: Remove Max Number of Edges to Keep Graph Fully Traversable, and it is one of the cleanest applications of Union-Find with a greedy twist. The problem forces you to think about what "minimum connectivity" means when two people share some edges but have their own private ones too.

Why this problem matters

Graph connectivity is a fundamental concept in computer science. This problem layers on a twist: two separate users need to traverse the same graph, but they each have exclusive edges plus shared ones. That dual-connectivity requirement shows up in real systems like network design, where you might need redundancy for different types of traffic.

Union-Find (also called Disjoint Set Union) is the go-to data structure for dynamic connectivity queries. If you have not drilled Union-Find yet, this problem is a strong reason to start. It combines the data structure with a greedy strategy that is elegant and interview-friendly.

The key insight

Type 3 edges are strictly better than type 1 or type 2 edges because they serve both Alice and Bob simultaneously. If you process type 3 edges first, each one you keep reduces the connectivity requirement for both users at once. After handling all the shared edges, you only add type 1 edges that Alice still needs and type 2 edges that Bob still needs.

This greedy ordering maximizes the number of removable edges. Any type 3 edge that connects two previously disconnected components is essential for at least one user. Any type 1 or type 2 edge that connects already-connected components in its respective Union-Find is redundant and can be removed.

The algorithm uses two separate Union-Find structures: one tracking Alice's connectivity and one tracking Bob's. A type 3 edge gets attempted in both. A type 1 edge only goes into Alice's. A type 2 edge only goes into Bob's.

The solution

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n + 1))
        self.rank = [0] * (n + 1)
        self.components = n

    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return False
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        self.parent[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        self.components -= 1
        return True

def max_num_edges_to_remove(n, edges):
    alice = UnionFind(n)
    bob = UnionFind(n)
    removed = 0

    for t, u, v in edges:
        if t == 3:
            a = alice.union(u, v)
            b = bob.union(u, v)
            if not a and not b:
                removed += 1

    for t, u, v in edges:
        if t == 1:
            if not alice.union(u, v):
                removed += 1
        elif t == 2:
            if not bob.union(u, v):
                removed += 1

    if alice.components != 1 or bob.components != 1:
        return -1
    return removed

The code has two phases. First, it processes all type 3 edges. For each one, it attempts the union in both Alice's and Bob's Union-Find. If the edge is redundant in both (both unions return False), it can be removed. If the edge helps at least one of them, it must stay.

Second, it processes type 1 and type 2 edges. A type 1 edge that does not connect new components in Alice's Union-Find is redundant. Same logic for type 2 with Bob. After processing everything, if either Union-Find still has more than one component, full traversal is impossible and we return -1.

Notice the subtle detail with type 3 edges: we increment removed only when the edge is redundant for both Alice and Bob. If it helps Alice but not Bob (or vice versa), the edge must be kept because removing it would disconnect one of them.

Visual walkthrough

The walkthrough shows the greedy strategy in action. Processing the two type 3 edges first connects nodes 1, 2, and 3 for both Alice and Bob. Then Alice's edge [1,1,3] is redundant because nodes 1 and 3 are already connected via the type 3 path. That edge gets removed. Alice's edge [1,1,4] and Bob's edge [2,2,4] both connect node 4, which was still isolated. Both are needed. Final answer: 1 edge removed.

Complexity analysis

E is the number of edges and N is the number of nodes. alpha is the inverse Ackermann function, which grows so slowly it is effectively constant for all practical input sizes.

Time: We iterate through the edges twice (once for type 3, once for types 1 and 2). Each union and find operation takes O(alpha(N)) amortized time with path compression and union by rank. The total is O(E * alpha(N)), which is nearly O(E).

Space: Each Union-Find uses O(N) for its parent and rank arrays. We maintain two of them, so total extra space is O(N).

The building blocks

1. Union-Find with path compression and union by rank

The core data structure that tracks connected components efficiently:

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n + 1))
        self.rank = [0] * (n + 1)
        self.components = n

    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return False
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        self.parent[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        self.components -= 1
        return True

Path compression (the line self.parent[x] = self.parent[self.parent[x]]) flattens the tree during find, keeping future lookups fast. Union by rank ensures the shorter tree always gets attached under the taller one, preventing the structure from degenerating into a linked list. Together, these two optimizations bring the amortized cost per operation down to O(alpha(N)). The union method returns a boolean indicating whether the merge actually happened. That return value is the key signal for counting redundant edges.

2. Edge prioritization

The greedy strategy of processing shared edges before exclusive ones:

for t, u, v in edges:
    if t == 3:
        a = alice.union(u, v)
        b = bob.union(u, v)
        if not a and not b:
            removed += 1

for t, u, v in edges:
    if t == 1:
        if not alice.union(u, v):
            removed += 1
    elif t == 2:
        if not bob.union(u, v):
            removed += 1

This two-pass approach is what makes the solution greedy. By handling type 3 edges first, you give shared edges the highest priority. A type 3 edge that connects two components saves you from needing separate type 1 and type 2 edges to achieve the same connectivity. That means more type 1 and type 2 edges end up being redundant, which maximizes the removal count.

Edge cases

• Already fully connected with only type 3 edges: All type 1 and type 2 edges are removable. The answer equals the count of type 1 plus type 2 edges.
• No type 3 edges: Alice and Bob must each independently form a spanning tree. You need at least n - 1 type 1 edges and n - 1 type 2 edges.
• Impossible case: If after processing all edges either Alice or Bob still has more than one component, return -1. This happens when there are not enough edges of the right types.
• Single node (n = 1): Both Union-Find structures start with 1 component. Every edge is removable. Return the total edge count.
• Duplicate edges: Two edges of the same type connecting the same pair of nodes. The second one is always redundant and gets counted in removed.
• All edges are type 3: Process all of them in the first pass. Any edge that does not reduce both component counts is removable. This degenerates to finding a spanning tree and removing the rest.

From understanding to recall

You now see the full picture: prioritize shared edges, use two Union-Find structures, count the edges that fail to merge new components. The logic is clean and the code is concise. But writing it from scratch under interview pressure is a different challenge.

The Union-Find class alone has several details that trip people up: path compression inside find, rank comparison in union, the component counter, and the boolean return value. Then you need to remember the two-pass structure and the subtle condition for type 3 edges where both unions must fail before you count a removal. Spaced repetition turns these details from "things you understand" into "things you type automatically."

Related posts

• Course Schedule - Graph connectivity via topological sort
• Number of Islands - Connected components in a grid
• Accounts Merge - Union-Find for grouping related elements

CodeBricks breaks this problem into its Union-Find and edge-prioritization building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a graph connectivity problem shows up in your interview, you do not hesitate. You just write it.