get_scc

ソースコード

from titan_pylib.graph.get_scc import get_scc

view on github

展開済みコード

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

仕様

get_scc(G: list[list[int]]) → list[list[int]][source]