Source code for titan_pylib.graph.topological_sort

 1from heapq import heapify, heappush, heappop
 2
 3# len(toposo) != n: 閉路が存在
 4
 5

[docs]
 6def topological_sort_min(G: list[list[int]]) -> list[int]:
 7    n = len(G)
 8    d = [0] * n
 9    F = [[] for _ in range(n)]
10    for i in range(n):
11        for x in G[i]:
12            d[x] += 1
13            F[x].append(i)
14    hq = [i for i, a in enumerate(d) if not a]
15    heapify(hq)
16    ret = []
17    while hq:
18        v = heappop(hq)
19        ret.append(v)
20        for x in F[v]:
21            d[x] -= 1
22            if d[x] == 0:
23                heappush(hq, x)
24    return ret

25
26

[docs]
27def topological_sort(G: list[list[int]]) -> list[int]:
28    """Return topological_sort. / O(|V|+|E|)"""
29    n = len(G)
30    d = [0] * n
31    outs = [[] for _ in range(n)]
32    for v in range(n):
33        for x in G[v]:
34            d[x] += 1
35            outs[v].append(x)
36    res = []
37    todo = [i for i in range(n) if d[i] == 0]
38    while todo:
39        v = todo.pop()
40        res.append(v)
41        for x in outs[v]:
42            d[x] -= 1
43            if d[x] == 0:
44                todo.append(x)
45    return res