DFSと木の親子関係

深さ優先探索は1本の枝を進んでから戻ります。Pythonでは深い再帰を避けるため、明示的なスタックも使えます。

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

前提：BFSで重みなし最短路

考え方

1. 未訪問の頂点をスタックへ積みます。
2. 木では親を覚えると戻る辺を区別できます。
3. 一般グラフでは親だけでなく訪問済み配列が必要です。

具体例

0が1と2につながる木で、order=[0,2,1] を得たとします。逆順なら子を親より先に処理できます。

実装

g = [[1,2],[0],[0]]
parent = [-1]*3
parent[0] = 0
order = []; stack = [0]
while stack:
    v = stack.pop(); order.append(v)
    for u in g[v]:
        if parent[u] == -1:
            parent[u] = v
            stack.append(u)
print(order)

注意する条件

再帰上限を上げてもメモリやスタックの問題が必ず解決するわけではありません。反復実装も選択肢です。

確認問題

4頂点の木の辺数は？

実装課題

N M と M 本の無向辺（0始まり）。連結成分数を求める。1 ≤ N ≤ 200000、0 ≤ M ≤ 200000。

入力:
4 2
0 1
2 3
出力:
2

n,m=map(int,input().split())
g=[[] for _ in range(n)]
for _ in range(m):
    u,v=map(int,input().split())
    g[u].append(v);g[v].append(u)
seen=[False]*n
ans=0
for s in range(n):
    if seen[s]: continue
    ans+=1;seen[s]=True;stack=[s]
    while stack:
        v=stack.pop()
        for u in g[v]:
            if not seen[u]:
                seen[u]=True;stack.append(u)
print(ans)

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