Applying connectivity to grouping

Understand the idea

Connectivity grouping needs an equivalence relation. DSU can merge accounts sharing identifiers, count components, or detect redundant undirected edges. Build explicit maps from identifiers to owners before merging.

Work through an example

Accounts sharing an email belong together through transitive connections. If A shares with B and B with C, all three join even when A and C share nothing directly.

Time and space complexity

Expected O(total identifiers) map work plus DSU operations; output sorting adds its own cost.

Why it works

Each shared identifier forces its participating records into one component.

Common mistakes

• Names alone may not prove identical ownership.
• Directed dependencies cannot be replaced by DSU.

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)