Source code for titan_pylib.graph.get_scc_lowlink

 1from titan_pylib.others.antirec import antirec
 2
 3

[docs]
 4def get_scc_lowlink(G: list[list[int]]) -> list[list[int]]:
 5    n = len(G)
 6    stack = [0] * n
 7    ptr = 0
 8    lowlink = [-1] * n
 9    order = [-1] * n
10    ids = [0] * n
11    cur_time = 0
12    group_cnt = 0
13
14    @antirec
15    def dfs(v: int):
16        nonlocal cur_time, ptr
17        order[v] = cur_time
18        lowlink[v] = cur_time
19        cur_time += 1
20        stack[ptr] = v
21        ptr += 1
22        for x in G[v]:
23            if order[x] == -1:
24                yield dfs(x)
25                lowlink[v] = min(lowlink[v], lowlink[x])
26            else:
27                lowlink[v] = min(lowlink[v], order[x])
28        if lowlink[v] == order[v]:
29            nonlocal group_cnt
30            while True:
31                u = stack[ptr - 1]
32                ptr -= 1
33                order[u] = n
34                ids[u] = group_cnt
35                if u == v:
36                    break
37            group_cnt += 1
38        yield
39
40    for v in range(n):
41        if order[v] == -1:
42            dfs(v)
43    groups = [[] for _ in range(group_cnt)]
44    for v in range(n):
45        groups[group_cnt - 1 - ids[v]].append(v)
46    return groups