Part7.14ダイナミックプログラミング(Dynamic Programming)位相整列(グラフィック整列)

質問する

位相整列とは


事全体の順序は一六二五四三に決めることができる.物事全体の順序にはいろいろな種類がある.
その一つです.

入力

1行目は、全体の個数Nと全体の順序情報の個数Mを与える.
2行目はM個の情報の提供を開始する.

しゅつりょく

日付全体の順序を出力します.

正解を解く

方向図の2 Dリストで値を初期化します.

便を確認し、「進入便」を最初の便リストに蓄積します.

Dequeを使用します.入力回数のないノード(すなわち、タスクを先に実行しても構わないノード)をdequeに添付します.

作業する幹線の数が1減る.

dequeが空になるまで繰り返します.

正しいコード

import sys
sys.stdin = open ("input.txt", "rt")
from collections import deque

def input():
    return sys.stdin.readline().rstrip()

if __name__ == "__main__":
    #n은 일의 개수 m은 정보의 개수
    n,m = map(int,input().split())
    graph = [[0]*(n+1) for _ in range(n+1)] # 인접행렬 기록 위한 이차원 리스트
    degree = [0]*(n+1) #진입차수 갸수 누적위한 일차원 리스트
    dQ = deque() # 큐활용

    for i in range(m):
        a,b = map(int,input().split())
        graph[a][b] = 1 #a 작업하고 b 작업하는 방향 그래프(즉 a에서 b로만 흐를 수 있다는 의미이다.)
        degree[b] += 1 #b로 진입하므로 진입차수 누적
    for i in range(1, n+1):
        if degree[i]==0: #차수가 0이면, 즉 선행될 작업이 없다면
            dQ.append(i) # dQ애 추가한다.
    while dQ:
        x=dQ.popleft()
        print(x,end=' ')
        for i in range(1, n+1):
            if graph[x][i]==1: #pop한 작업의 진입차수를 대상을 찾아 -1한다.(작업실행)
                degree[i] -= 1
                if degree[i]==0: #더 이상 할 일이 없다면 append 시킨다.
                    dQ.append(i)