Source code for titan_pylib.graph.get_scc_graph

 1from titan_pylib.others.antirec import antirec
 2
 3

[docs]
 4def get_scc_graph(G: list[list[int]]):
 5    """
 6    scc, 頂点を縮約した隣接リスト, もとの頂点->新たなグラフの頂点
 7    """
 8    n = len(G)
 9    stack = [0] * n
10    ptr = 0
11    lowlink = [-1] * n
12    order = [-1] * n
13    ids = [0] * n
14    cur_time = 0
15    group_cnt = 0
16
17    @antirec
18    def dfs(v: int):
19        nonlocal cur_time, ptr
20        order[v] = cur_time
21        lowlink[v] = cur_time
22        cur_time += 1
23        stack[ptr] = v
24        ptr += 1
25        for x in G[v]:
26            if order[x] == -1:
27                yield dfs(x)
28                lowlink[v] = min(lowlink[v], lowlink[x])
29            else:
30                lowlink[v] = min(lowlink[v], order[x])
31        if lowlink[v] == order[v]:
32            nonlocal group_cnt
33            while True:
34                u = stack[ptr - 1]
35                ptr -= 1
36                order[u] = n
37                ids[u] = group_cnt
38                if u == v:
39                    break
40            group_cnt += 1
41        yield
42
43    for v in range(n):
44        if order[v] == -1:
45            dfs(v)
46    groups = [[] for _ in range(group_cnt)]
47    for v in range(n):
48        groups[group_cnt - 1 - ids[v]].append(v)
49
50    F = [set() for _ in range(max(ids) + 1)]
51    for v in range(n):
52        for x in G[v]:
53            if ids[v] != ids[x]:
54                F[ids[v]].add(ids[x])
55    F = [list(f) for f in F]
56    return groups, F, ids