Disjoint-set operations

What are graph ordering and connectivity?

Graph ordering asks which sequence respects the connections in a graph. Connectivity asks which vertices can reach one another. For prerequisite relationships, a topological order puts each prerequisite before the task that needs it. It exists only when the directed graph has no cycle.

Example: If task A must finish before B, and B before C, A, B, C is a valid order. Adding a requirement that C must finish before A creates a cycle, so no such order exists.

Helpful before this chapter

If these ideas are new, begin with:

Graph representations and traversal

Understand the idea

DSU maintains a partition into disjoint sets. find returns a representative; union merges two sets. Representatives are implementation details, not necessarily smallest members or original graph roots.

Work through an example

union(0,1), union(1,2) make 0,1,2 equivalent. Vertex 3 remains separate. A repeated union returns False because no partition change occurs.

Time and space complexity

With compression and size/rank, amortized O(α(V)) operations; O(V) storage.

Why it works

Two elements are connected exactly when their representatives agree.

Common mistakes

DSU does not recover a connecting path.
Ordinary DSU does not support arbitrary edge deletion.

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)

CHECK YOUR UNDERSTANDING

What are graph ordering and connectivity?

Only 0 has no unmet prerequisites.