AOJ GRL_4_B Topological Sort

備忘録

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_4_B&lang=jp

回答

import sys, os, math, bisect, itertools, collections, heapq, queue, copy, array

# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
# from decimal import Decimal
# from collections import defaultdict, deque

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

MOD = 10 ** 9 + 7
INF = float('inf')


def topological_sort(graph, indeg, visited, ans, N):
    for n in range(N):
        if indeg[n] == 0 and visited[n] == -1:
            visited[n] = 0
            que = collections.deque([n])
            while que:
                now = que.pop()
                ans.append(now)
                for next in graph[now]:
                    indeg[next] -= 1
                    if indeg[next] == 0:
                        que.append(next)
                        visited[next] = 1


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    V, E = il()
    indeg = [0 for _ in range(V)]
    visited = collections.defaultdict()
    for v in range(V):
        visited[v] = -1
    graph = collections.defaultdict(list)
    for _ in range(E):
        s, t = il()
        graph[s].append(t)
        indeg[t] += 1
    ans = []

    topological_sort(graph, indeg, visited, ans, V)
    print(*ans, sep='\n')


if __name__ == '__main__':
    main()

考え方

螺旋本より、トポロジカルソート問題。
有向グラフを左から右へ向かうようにソートを行う。
俗にいうクリティカルパスの作業順ソート。

実装は基本的に螺旋本の通り。
与えられた有向グラフに対して、入り次数が0のノードを起点に、
幅優先探索を行なう。
起点に連なったノードの入り次数を減らして、入り次数が０のノート（作業を開始可能なノード）をキューに積む。