トポロジカルソートと閉路検出

トポロジカルソート
有向グラフの閉路の検出とトポロジカルソート

• 閉路あり→ -1
• 閉路なし→ list（任意の有向辺に対し）

計算量
　( :頂点数, :辺の数)

def topo_sort(g,n):
    order=[]
    indeg=[0]*n
    for v in range(n):
        for v1 in g[v]:
            indeg[v1]+=1
    st=[v for v in range(n) if indeg[v]==0]
    while st:
        v=st.pop()
        order.append(v)
        for v1 in g[v]:
            indeg[v1]-=1
            if indeg[v1]==0:
                st.append(v1)
    if len(order)==n:
        return order
    return -1                       #閉路あり

(stackはqueueでもheapqでもなんでも良い)

使い方

#  ↑→→↓
#  0  1 
#  ↓→→↑ の時
n=2
g=[[1],[0]]
print(topo_sort(g,n))

#  0→1→2
#    ↓ ↑
#    3→4
n=5
g=[[1],[2,3],[],[4],[2]]
print(topo_sort(g,n))

例題
ABC223D
ABC139E

参考
木上のトポロジカルソートのコード、強連結成分分解のコードを近日中載せます。