Pythonアルゴリズム082|位相整列(グラフィック整列)

14949 ワード
パイ アルゴリズム問題 テキストリンク

82.位相位置合わせ（グラフィック位置合わせ）


位相位置合わせは、ある操作順序を実行するアルゴリズムです.
それぞれの事の前後関係が複雑である場合、それぞれの事の前後関係を維持しています.
ソートアルゴリズム.
以下の順序で並べ替えると、作業全体の順序が決まります.
1/4番の仕事をした後、4番の仕事をします.
5 4
4 3
2 5
2 3
6 2

事全体の順序は一六二五四三に決めることができる.物事全体の順序にはいろいろな種類がある.
その一つです.
■説明の入力
1行目は、全体の個数Nと全体の順序情報の個数Mを与える.
2行目はM個の情報の提供を開始する.
■出力説明
日付全体の順序を出力します.
■入力例1
6 6
1 4
5 4
4 3
2 5
2 3
6 2
■出力例1
1 6 2 5 4 3

『私の答え』


方法がわからない

<解答>


  • 入場回数:予め完了したタスク
  • の入場車数の値を入力し、柔軟に入れて削除します.
    対応する操作(度数から減算)
    • 
import sys
from collections import deque
sys.stdin=open("input.txt", "r")
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
    degree[b]+=1 #진입차수 수를 갱신해주는 것
for i in range(1, n+1):
    if degree[i]==0: #차수가 0이라서 선행해야 할 작업이 없는 애는 바로 q에 넣어버리면 됨
        dQ.append(i)
while dQ:
    x=dQ.popleft()
    print(x, end=' ')
    for i in range(1, n+1):
        if graph[x][i]==1: #얘가 진입차수 였던 애들한테서 진입차수의 갯수 하나씩 빼주기
            degree[i]-=1
            if degree[i]==0: #진입차수가 0이 되면 앞에서 더이상 처리해줄 값이 없으니깐 q에 넣어주기
                dQ.append(i)

    『反省点』


    『学んだこと』


  • 位相位置合わせでは、入力回数が重要です(私の入力方向の数)

  • 各ノードの入場回数を入力*

  • キューの使用

    <第2ラウンド解答>


    •  
n,m=map(int,input().split())
dy=[0]*(n+1)
for i in range(m) :
    a,b=map(int,input().split())
    dy[b]+=1
print(dy)
    =>入车数のカウントダウンしか覚えていません.
    =>講義を聞いた後の回答:
    
from collections import deque
n,m=map(int,input().split())
g=[[0]*(n+1) for _ in range(n+1)]
degree=[0]*(n+1)
q=deque()
p=[]

for i in range(m) :
    a,b=map(int,input().split())
    g[a][b]=1
    degree[b]+=1
for i in range(1,n+1) : 
    if degree[i]==0:
        q.append(i)
while q:
    k=q.popleft()
    p.append(k)
    for i in range(1,n+1) :
            if g[k][i]==1 :
                degree[i]-=1
                if degree[i]==0:
                    q.append(i)
print(p)
    BOJ:10808文字数(C++)
    webhacking.解答61番、5番、7番