topological_sort¶
ソースコード¶
from titan_pylib.graph.topological_sort import topological_sort_min
from titan_pylib.graph.topological_sort import topological_sort
展開済みコード¶
1# from titan_pylib.graph.topological_sort import topological_sort
2from heapq import heapify, heappush, heappop
3
4# len(toposo) != n: 閉路が存在
5
6
7def topological_sort_min(G: list[list[int]]) -> list[int]:
8 n = len(G)
9 d = [0] * n
10 F = [[] for _ in range(n)]
11 for i in range(n):
12 for x in G[i]:
13 d[x] += 1
14 F[x].append(i)
15 hq = [i for i, a in enumerate(d) if not a]
16 heapify(hq)
17 ret = []
18 while hq:
19 v = heappop(hq)
20 ret.append(v)
21 for x in F[v]:
22 d[x] -= 1
23 if d[x] == 0:
24 heappush(hq, x)
25 return ret
26
27
28def topological_sort(G: list[list[int]]) -> list[int]:
29 """Return topological_sort. / O(|V|+|E|)"""
30 n = len(G)
31 d = [0] * n
32 outs = [[] for _ in range(n)]
33 for v in range(n):
34 for x in G[v]:
35 d[x] += 1
36 outs[v].append(x)
37 res = []
38 todo = [i for i in range(n) if d[i] == 0]
39 while todo:
40 v = todo.pop()
41 res.append(v)
42 for x in outs[v]:
43 d[x] -= 1
44 if d[x] == 0:
45 todo.append(x)
46 return res