Source code for titan_pylib.graph.get_scc


[docs]
 1def get_scc(G: list[list[int]]) -> list[list[int]]:
 2    n = len(G)
 3    rG = [[] for _ in range(n)]
 4    for v in range(n):
 5        for x in G[v]:
 6            rG[x].append(v)
 7    visited = [0] * n
 8    dfsid = [0] * n
 9    now = n
10    for s in range(n):
11        if visited[s]:
12            continue
13        todo = [~s, s]
14        while todo:
15            v = todo.pop()
16            if v >= 0:
17                if visited[v]:
18                    continue
19                visited[v] = 2
20                for x in G[v]:
21                    if visited[x]:
22                        continue
23                    todo.append(~x)
24                    todo.append(x)
25            else:
26                v = ~v
27                if visited[v] == 1:
28                    continue
29                visited[v] = 1
30                now -= 1
31                dfsid[now] = v
32    res = []
33    for s in dfsid:
34        if not visited[s]:
35            continue
36        todo = [s]
37        visited[s] = 0
38        for v in todo:
39            for x in rG[v]:
40                if not visited[x]:
41                    continue
42                visited[x] = 0
43                todo.append(x)
44        res.append(todo)
45    # 閉路検出: len(res) == n
46    return res