Union by rank/size

Understand the idea

Union by size attaches the smaller tree to the larger root. Rank approximates height and is updated only when equal-rank roots merge. Compression means rank is no longer actual current height.

Work through an example

Merging groups of sizes 3 and 1 attaches the one-member root beneath the three-member root; the surviving size becomes 4.

Time and space complexity

Without compression, size balancing bounds height O(log V); combined amortized O(α(V)).

Why it works

Stored size is accurate only at representatives, and parent links connect equivalent elements.

Common mistakes

• Updating the losing root size alone is wrong.
• Do not compare sizes of arbitrary non-root nodes.

Chapter lab · Python implementation

Dependency order and connectivity answer different questions. Kahn topological sorting removes zero-indegree vertices from a directed graph. Disjoint-set union merges undirected connectivity groups without maintaining paths. The lab implements both; choose the structure whose contract matches the question.

This shared lab connects the chapter's topics. Follow the current lesson's worked example first, then trace the complete implementation. Additional algorithms described in topic exercises are variations you can implement independently.

from collections import deque

def topological(n,edges):
    graph=[[] for _ in range(n)]; indegree=[0]*n
    for a,b in edges:
        graph[a].append(b); indegree[b]+=1
    queue=deque(i for i in range(n) if indegree[i]==0)
    order=[]
    while queue:
        a=queue.popleft(); order.append(a)
        for b in graph[a]:
            indegree[b]-=1
            if indegree[b]==0: queue.append(b)
    return order if len(order)==n else None

class DSU:
    def __init__(self,n):
        self.parent=list(range(n)); self.size=[1]*n
    def find(self,x):
        while x!=self.parent[x]:
            self.parent[x]=self.parent[self.parent[x]]
            x=self.parent[x]
        return x
    def union(self,a,b):
        a,b=self.find(a),self.find(b)
        if a==b: return False
        if self.size[a]<self.size[b]: a,b=b,a
        self.parent[b]=a; self.size[a]+=self.size[b]
        return True

Run and test the lab

Copy the implementation and these assertions into a Python 3 file and run it. An assertion failure means the actual result differs from the expectation. Add the current topic's exercise and boundary tests to deepen your understanding.

assert topological(4,[(0,1),(0,2),(1,3),(2,3)])==[0,1,2,3]
assert topological(2,[(0,1),(1,0)]) is None
d=DSU(4); assert d.union(0,1) and d.union(1,2)
assert d.find(0)==d.find(2) and not d.union(0,2)
assert d.find(3)!=d.find(0)