Path compression

Understand the idea

Path compression shortens find paths by redirecting nodes toward the representative. Full compression or path halving preserve connectivity while making later lookups cheaper.

Work through an example

A chain 4→3→2→0 can be shortened to direct or near-direct links to 0. The lab uses halving: parent[x]=parent[parent[x]].

Time and space complexity

Combined with balancing, amortized O(α(V)); one operation is not promised worst-case constant.

Why it works

Compression changes parent shape but never set membership or the final representative.

Common mistakes

• Only roots represent sets.
• Do not change parent links to a non-equivalent component.

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)