55 lines
1.8 KiB
Python
55 lines
1.8 KiB
Python
"""Iterative Tarjan strongly connected components (no recursion limit)."""
|
|
from __future__ import annotations
|
|
|
|
from typing import Dict, Iterable, List, Tuple
|
|
|
|
|
|
def scc(adj: Dict[int, Iterable[int]]) -> List[List[int]]:
|
|
index_counter = [0]
|
|
stack: List[int] = []
|
|
on_stack: set = set()
|
|
indices: Dict[int, int] = {}
|
|
lowlink: Dict[int, int] = {}
|
|
result: List[List[int]] = []
|
|
|
|
for u in list(adj.keys()):
|
|
if u in indices:
|
|
continue
|
|
call_stack: List[Tuple[int, iter]] = [(u, iter(adj.get(u, ())))]
|
|
indices[u] = lowlink[u] = index_counter[0]
|
|
index_counter[0] += 1
|
|
stack.append(u)
|
|
on_stack.add(u)
|
|
while call_stack:
|
|
v, it = call_stack[-1]
|
|
advanced = False
|
|
for w in it:
|
|
if w not in indices:
|
|
indices[w] = lowlink[w] = index_counter[0]
|
|
index_counter[0] += 1
|
|
stack.append(w)
|
|
on_stack.add(w)
|
|
call_stack.append((w, iter(adj.get(w, ()))))
|
|
advanced = True
|
|
break
|
|
elif w in on_stack:
|
|
if indices[w] < lowlink[v]:
|
|
lowlink[v] = indices[w]
|
|
call_stack[-1] = (v, it)
|
|
if advanced:
|
|
continue
|
|
call_stack.pop()
|
|
if call_stack:
|
|
parent = call_stack[-1][0]
|
|
if lowlink[v] < lowlink[parent]:
|
|
lowlink[parent] = lowlink[v]
|
|
if lowlink[v] == indices[v]:
|
|
comp = []
|
|
while True:
|
|
w = stack.pop()
|
|
on_stack.discard(w)
|
|
comp.append(w)
|
|
if w == v:
|
|
break
|
|
result.append(comp)
|
|
return result |