DAG：依存関係の順に処理する

有向閉路がないグラフなら、すべての辺が前から後ろへ向く順序を作れます。DPの処理順としても使えます。

言語：Python / 計算量：O(V+E)

考え方

入次数0の頂点をキューへ。
取り出した頂点の辺を削るように入次数を減らします。
N個取り出せなければ閉路があります。

具体例

0→2、1→2 なら0と1を先に処理し、最後に2。順序は一意とは限りません。

実装

from collections import deque
g=[[2],[2],[]];deg=[0,0,2]
q=deque(i for i in range(3) if deg[i]==0);order=[]
while q:
    v=q.popleft();order.append(v)
    for u in g[v]:
        deg[u]-=1
        if deg[u]==0:q.append(u)
print(order)

注意する条件

一般グラフの最長路にそのまま使えません。DAGという条件が重要です。

確認問題

0→1→2 の最長路の辺数は？

解答と理由

頂点は3個でも、辺は2本です。

実装課題

N M と有向辺（0始まり）。DAGなら Yes、閉路があれば No。N,M ≤ 200000。

入力:
2 2
0 1
1 0
出力:
No

参考実装

from collections import deque
n,m=map(int,input().split());g=[[] for _ in range(n)];deg=[0]*n
for _ in range(m):
    u,v=map(int,input().split());g[u].append(v);deg[v]+=1
q=deque(i for i in range(n) if deg[i]==0);cnt=0
while q:
    v=q.popleft();cnt+=1
    for u in g[v]:
        deg[u]-=1
        if deg[u]==0:q.append(u)
print("Yes" if cnt==n else "No")

読了の記録・下書き・メモへ