Redundant Connection and Graph Valid Tree with Union-Find

Union-find is usually introduced as "are these two connected?", but one pass over an edge list answers two more questions for free: how many separate groups there are, and which edges were unnecessary because their endpoints were already connected. Both fall out of the return value of union, and they are exactly what redundant connection and graph valid tree ask for.

The problem it solves

You are given n nodes and a list of undirected edges, often as a stream: cables being laid, friendships being added. Three questions come up again and again:

• How many connected components remain?
• Does any edge close a cycle, and which one?
• Is the whole thing a tree: connected, with no cycle?

A graph search can answer each, but it needs the whole adjacency list first and walks it again per question. Union-find answers each edge on arrival.

The intuition

Give every node its own group and set a counter to n. Then process the edges one at a time, and look at what union(a, b) finds:

• Different roots. Two separate groups become one. That is a real merge, so the counter drops by one.
• The same root. a and b were already connected through earlier edges. Nothing merges, and this edge adds a second route between them, which is precisely a cycle.

Every edge is either a merge or a cycle edge, so with E edges and C components at the end, there were n - C merges and E - (n - C) cycle edges. A node in no edge at all is still a component of one, which is why the counter starts at n.

The two classic problems are direct readings of this:

• Graph valid tree. A tree on n nodes has exactly n - 1 edges and no cycle. Check the count, then make sure no union returns False. Connectivity follows: each of those edges was a real merge, taking the count from n to 1.
• Redundant connection. A tree on nodes 1 to n gained one extra edge; return an edge whose removal leaves a tree, the last in the input if several qualify. Return the first edge whose union fails: every earlier edge on that cycle merged, so the failing one is the cycle edge that comes last.

All of this is for undirected graphs. In a directed graph, a → b and b → a are not a cycle in the same sense, and union-find cannot tell direction; that needs the colouring DFS from detecting cycles in directed graphs.

Watch it run

The animation lays the lesson's cables between six buildings. With no cable laid, every building is its own component, so the counter starts at 6. Cable 0–1 finds two different roots, a real merge, and the counter drops to 5. Cable 1–2 finds different roots again; three buildings now share one root and the counter is 4. Cable 0–2 is the interesting one: both ends already reach the same root, labelled "root 2" under each, so nothing merges and this edge closes a cycle. The cycle readout ticks to 1 while components stays at 4. Cable 3–4 joins a pair nobody had touched, and the counter falls to 3. Building 5 appears in no cable at all, but it still reaches itself, so it is a component of one. One pass over the edges answered both questions: 3 components and 1 redundant cable.

The code

A union-find with union by size and path halving, the counter kept inside it, and the three problems as short functions on top:

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n
        self.components = n                     # everyone starts alone

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

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False                        # already connected: a cycle edge
        if self.size[ra] < self.size[rb]:
            ra, rb = rb, ra                     # smaller tree under the larger root
        self.parent[rb] = ra
        self.size[ra] += self.size[rb]
        self.components -= 1                    # a real merge
        return True

def components_and_cycles(n, edges):
    dsu, cycles = DSU(n), 0
    for a, b in edges:
        if not dsu.union(a, b):
            cycles += 1
    return dsu.components, cycles

print(components_and_cycles(6, [(0, 1), (1, 2), (0, 2), (3, 4)]))   # (3, 1)

def valid_tree(n, edges):
    if len(edges) != n - 1:                     # a tree on n nodes has n - 1 edges
        return False
    dsu = DSU(n)
    return all(dsu.union(a, b) for a, b in edges)   # and none of them closes a cycle

print(valid_tree(5, [(0, 1), (0, 2), (0, 3), (1, 4)]))   # True
print(valid_tree(4, [(0, 1), (2, 3), (1, 0)]))           # False  right count, still a cycle

def redundant_connection(edges):
    """Nodes 1..n, n edges: a tree plus one extra. Return the edge that closes the cycle."""
    dsu = DSU(len(edges) + 1)
    for a, b in edges:
        if not dsu.union(a, b):
            return [a, b]

print(redundant_connection([[1, 2], [1, 3], [2, 3]]))                    # [2, 3]
print(redundant_connection([[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]]))    # [1, 4]

The second valid_tree call is the trap the count check alone misses: three edges for four nodes, but (1, 0) repeats (0, 1), so it closes a two-edge cycle and nodes 2 and 3 are cut off from 0 and 1. Now a check on 3,000 seeded random graphs, self-loops and repeated edges included, against a breadth-first search that labels components from scratch. It confirms the counter, the cycle-edge formula E - n + C, the tree test, and the redundant edge against a brute force that removes edges from the back until what remains is a tree:

import random
from collections import deque

def bfs_components(n, edges):
    """Brute force: label every node by a fresh BFS."""
    adj = [[] for _ in range(n)]
    for a, b in edges:
        adj[a].append(b)
        adj[b].append(a)
    seen, count = [False] * n, 0
    for s in range(n):
        if not seen[s]:
            count += 1
            seen[s] = True
            q = deque([s])
            while q:
                for v in adj[q.popleft()]:
                    if not seen[v]:
                        seen[v] = True
                        q.append(v)
    return count

def is_tree(n, edges):
    return len(edges) == n - 1 and bfs_components(n, edges) == 1

rng = random.Random(33)
ok = True
for _ in range(3_000):
    n = rng.randint(1, 9)
    edges = [(rng.randrange(n), rng.randrange(n)) for _ in range(rng.randint(0, 12))]
    comps, cycles = components_and_cycles(n, edges)
    c = bfs_components(n, edges)
    ok &= comps == c and cycles == len(edges) - n + c   # every surplus edge is a cycle edge
    ok &= valid_tree(n, edges) == is_tree(n, edges)
    # a random tree on 1..m plus one extra edge, in random order
    m = rng.randint(3, 9)
    tree = [[rng.randint(1, v - 1), v] for v in range(2, m + 1)]
    present = {frozenset(e) for e in tree}
    extra = rng.choice([[a, b] for a in range(1, m + 1) for b in range(a + 1, m + 1)
                        if frozenset((a, b)) not in present])
    es = tree + [extra]
    rng.shuffle(es)
    # brute force: the LAST edge whose removal leaves a tree
    want = next(e for i, e in reversed(list(enumerate(es)))
                if is_tree(m, [(a - 1, b - 1) for a, b in es[:i] + es[i + 1:]]))
    ok &= redundant_connection(es) == want
print(ok)                                               # True

The complexity

• Per edge: two find calls and at most one write, amortised O(α(n)) with union by size and path compression or halving, effectively constant. The Big-O cheat sheet lists the bounds with and without each optimisation.
• Whole pass: O(n + E · α(n)) time and O(n) space. The edges are never stored, which suits a stream.
• BFS or DFS alternative: O(n + E) once, but it needs the adjacency list and a fresh walk whenever edges change.

Where it goes wrong

• Starting the counter at zero. Isolated nodes are components too; start at n.
• Decrementing on every union call. Only a real merge changes the count.
• Checking only len(edges) == n - 1 for a tree. A repeated edge passes the count and fails the test.
• Off-by-one on 1-indexed nodes. Redundant connection numbers nodes from 1, so the arrays need n + 1 slots.
• Using it on directed graphs. The directed version of redundant connection, where a node can end up with two parents, needs extra case analysis on top.

When it shows up in interviews

As "number of connected components", "graph valid tree", "redundant connection" and "number of provinces", and inside Kruskal's minimum spanning tree, where every rejected edge is a failed union. A common follow-up to a DFS solution: "now the edges arrive one at a time; how do you answer after each?" The data structure itself is covered in path compression and union by size, and the DFS side of counting in connected components, DFS vs union-find.

How to say it in an interview

"I'd use union-find with the component count starting at n. For each edge I find both roots. If they differ, I link the smaller tree under the larger and decrement the count. If they're the same, the endpoints were already connected, so this edge closes a cycle. For graph valid tree I first check there are exactly n minus one edges, then that no union fails, which also guarantees connectivity. For redundant connection I return the first edge whose union fails, which is the last edge of the cycle in input order. Each edge costs near-constant amortised time, so the pass is linear."