117 lines
3.3 KiB
Python
117 lines
3.3 KiB
Python
"""Tarjan's strongly connected components (SCC) algorithm.
|
|
|
|
Iterative DFS to avoid recursion limits; verified against a brute-force
|
|
reachability SCC on 2000 random directed graphs.
|
|
"""
|
|
import random
|
|
import sys
|
|
|
|
|
|
def tarjan_scc(n, edges):
|
|
adj = [[] for _ in range(n)]
|
|
for u, v in edges:
|
|
adj[u].append(v)
|
|
|
|
index_counter = [0]
|
|
stack = []
|
|
on_stack = [False] * n
|
|
indices = [-1] * n
|
|
lowlink = [0] * n
|
|
result = []
|
|
|
|
for start in range(n):
|
|
if indices[start] != -1:
|
|
continue
|
|
work = [(start, 0)]
|
|
indices[start] = lowlink[start] = index_counter[0]
|
|
index_counter[0] += 1
|
|
stack.append(start)
|
|
on_stack[start] = True
|
|
|
|
while work:
|
|
u, pi = work[-1]
|
|
if pi < len(adj[u]):
|
|
work[-1] = (u, pi + 1)
|
|
v = adj[u][pi]
|
|
if indices[v] == -1:
|
|
indices[v] = lowlink[v] = index_counter[0]
|
|
index_counter[0] += 1
|
|
stack.append(v)
|
|
on_stack[v] = True
|
|
work.append((v, 0))
|
|
elif on_stack[v]:
|
|
if indices[v] < lowlink[u]:
|
|
lowlink[u] = indices[v]
|
|
else:
|
|
if lowlink[u] == indices[u]:
|
|
comp = []
|
|
while True:
|
|
w = stack.pop()
|
|
on_stack[w] = False
|
|
comp.append(w)
|
|
if w == u:
|
|
break
|
|
result.append(comp)
|
|
work.pop()
|
|
if work:
|
|
parent = work[-1][0]
|
|
if lowlink[u] < lowlink[parent]:
|
|
lowlink[parent] = lowlink[u]
|
|
return result
|
|
|
|
|
|
def brute_scc(n, edges):
|
|
adj = [[False] * n for _ in range(n)]
|
|
for u, v in edges:
|
|
adj[u][v] = True
|
|
for k in range(n):
|
|
for i in range(n):
|
|
if adj[i][k]:
|
|
row_i = adj[i]
|
|
row_k = adj[k]
|
|
for j in range(n):
|
|
if row_k[j]:
|
|
row_i[j] = True
|
|
seen = [False] * n
|
|
comps = []
|
|
for i in range(n):
|
|
if seen[i]:
|
|
continue
|
|
comp = [j for j in range(n) if not seen[j] and adj[i][j] and adj[j][i]]
|
|
if i not in comp:
|
|
comp.append(i)
|
|
for j in comp:
|
|
seen[j] = True
|
|
comps.append(comp)
|
|
return comps
|
|
|
|
|
|
def normalize(comps):
|
|
return sorted(sorted(c) for c in comps)
|
|
|
|
|
|
def self_test():
|
|
random.seed(42)
|
|
for t in range(2000):
|
|
n = random.randint(1, 12)
|
|
m = random.randint(0, n * n)
|
|
edges = [(random.randrange(n), random.randrange(n)) for _ in range(m)]
|
|
a = normalize(tarjan_scc(n, edges))
|
|
b = normalize(brute_scc(n, edges))
|
|
if a != b:
|
|
print("MISMATCH", n, edges)
|
|
print("tarjan", a)
|
|
print("brute", b)
|
|
return False
|
|
assert normalize(tarjan_scc(0, [])) == []
|
|
assert normalize(tarjan_scc(1, [])) == [[0]]
|
|
assert normalize(tarjan_scc(3, [(0, 1), (1, 2), (2, 0)])) == [[0, 1, 2]]
|
|
assert normalize(tarjan_scc(3, [(0, 1), (1, 2)])) == [[0], [1], [2]]
|
|
print("ALL TESTS PASSED (2000 random + edge cases)")
|
|
return True
|
|
|
|
|
|
if __name__ == "__main__":
|
|
ok = self_test()
|
|
sys.exit(0 if ok else 1)
|