memo: pythonで post-order traversalをnon-recursiveにやる!

intro

• 備忘録的メモです。

motivation

• pythonで、dsfの帰りがけ順序探索(post-order-traversal)をやるときに、非再帰で実装したい

issue

• TLEしてしまう。
  • おそらく、下のような実装になるはずで。
  • while文の中の、 for nex in adj[node]:の部分が、遅い
    • nodeに戻ってくるたびに、このfor文が回ってしまう
    • すでに訪問済みのnexには、もう行かないので、無駄なloopが回っている。

N = num_node
adj = [[] for _ in raneg(N)]  # 隣接list

# adjを問題に沿って、構築する
visited = [False]*N
# post_orderを記録する
post_order = []

# dfsをstackを使って再現
for s in range(N):
    stack = [s]
    visited[s] = True

    while stack:
        node = stack.pop()
        for nex in adj[node]:  # お隣さんに移動する
            if visited[nex]:
                continue
                # stackにnodeとnexをこの順で入れることで、dfsできる
                stack.append(node)
                stack.append(nex)
                visited[nex] = True
                break
        else:  # breakされなかったら通る(nodeより先(startから遠い)のnodeはすでに訪問した場合
            post_order.append(node)

solution

• すでに訪問したnodeは,adjから消す

pro&cons

• pro: 早くなる
  • adjがloopのたびに短くなるので、for nex in adj[node] が軽くなる。)
• cons: adjが破壊される
  • あとで再利用とかしたい時は、copyを作ってからやる。

code

• before: for nex in adj[s]
• after: while adj[s]: nex = adj[s].pop()

for s in range(N):
    stack = [s]
    visited[s] = True

    while stack:
        node = stack.pop()
        while adj[node]: #<=<=<= ここが変更点
             nex = adj[node].pop() #<=<= adjに対する破壊的操作
            if visited[nex]:
                continue
                
                stack.append(node)
                stack.append(nex)
                visited[nex] = True
                break
        else:  # breakされなかったら通る(nodeより先(startから遠い)のnodeはすでに訪問した場合
            post_order.append(node)

summary

• pythonで、post-order-traversalの時に、non-recursion実装を早くする方法のメモ
• (再帰実装でも、TLEしないと思うけど)
• SCC分解の時に困ったので、使った。