はじめに
競プロ典型90問 021 - Come Back in One Piece（★5）を考えていたのですが、解説を見てもACが取れず、DFSとして使っていたコードが実はDFSになっていなかったことに気が付きました。
どういうこと？
結論としては、各頂点の確認済みのフラグを立てるタイミングを間違えていたみたいです。
以下、$N$ を頂点数、$d$ を隣接リストとして、グラフの各頂点の番号を順に出力することを考えます。
正しいコード
# N: 頂点数, d[v]: vに隣接している頂点の配列
start = 0
todo = [start]
seen = [False] * N
while todo:
v = todo.pop()
if seen[v]:
continue
seen[v] = True # フラグを立てる
print(v) # 各頂点での処理
for w in d[v]: # 辺を調べる
if seen[w]:
continue
todo.append(w) # 次の頂点をtodoに追加
各辺に対しては、次の頂点 w をスタック todo に追加するだけです。
間違えていたコード
# N: 頂点数, d[v]: vに隣接している頂点の配列
start = 0
todo = [start]
seen = [False] * N
seen[start] = True
while todo:
v = todo.pop()
print(v) # 各頂点での処理
for w in d[v]: # 辺を調べる
if seen[w]:
continue
todo.append(w) # 次の頂点をtodoに追加
seen[w] = True # フラグを立てる
各辺に対して、次の頂点 w をスタック todo に追加して、フラグ seen[w] を立てています。辺を見てすぐにフラグを立てることで、今いる頂点 v から隣接する全ての頂点 w への経路を確定することになり、「深さ優先」でなくなっています。
具体例
簡単な例を紹介します。
次のグラフにおける $0$ を根としたDFSを考えます。
「深さ優先」という性質に注意すると、このDFSでは、以下のどちらかが成り立つはずです。
- 頂点 $1$ の直後に頂点 $3$ を見る
- 頂点 $3$ の直後に頂点 $1$ を見る
入力は以下のようにとります。
N = 4
d = [[3, 2, 1], [3, 0], [0], [1, 0]]
先ほど紹介した「正しいコード」「間違えていたコード」の実行結果は次のようになります。
正しいコード
N = 4
d = [[3, 2, 1], [3, 0], [0], [1, 0]]
start = 0
todo = [start]
seen = [False] * N
while todo:
v = todo.pop()
if seen[v]:
continue
seen[v] = True # フラグを立てる
print(v) # 各頂点での処理
for w in d[v]: # 辺を調べる
if seen[w]:
continue
todo.append(w) # 次の頂点をtodoに追加
1 の直後に 3 が出力されます。
0
1
3
2
間違えていたコード
N = 4
d = [[3, 2, 1], [3, 0], [0], [1, 0]]
start = 0
todo = [start]
seen = [False] * N
seen[start] = True
while todo:
v = todo.pop()
print(v) # 各頂点での処理
for w in d[v]: # 辺を調べる
if seen[w]:
continue
todo.append(w) # 次の頂点を追加
seen[w] = True # フラグを立てる
1 の直後に 3 が出力されず、間に 2 が入ってしまいます。
0
1
2
3
さいごに
約一年ほど競プロをしていますが、ずっと嘘のDFSを使っていたと思うとぞっとします...。
ただ「正しいコード」に比べると「間違えていたコード」はスタックに入れる情報が少なく、計算量的には若干程度は優秀なのかなと思います。到達可能判定や、ただの連結成分への分解ではバグにはならないはずなので、TLEに悩まされたら使ってみる価値もあるかも。
一応、冒頭で触れた 競プロ典型90問 021 - Come Back in One Piece（★5） の提出も貼っておきます。