結論：ABC251 Fでは、頂点1から深さ優先探索で初めて発見した辺を集めた木をT1、幅優先探索で初めて発見した辺を集めた木をT2として出力します。T1は非木辺の両端が祖先・子孫関係になる条件に合い、T2はそのような非木辺を持たない条件に合います。単純・連結な無向グラフという問題の前提が、この二つの性質を支えます。
一問の解答としてはABC251 Fの条件、構成、Pythonコード、正しさを確認します。手法の学習としては、同じ小さなグラフでDFSとBFSの発見順を追い、最後にBFSの親構成とDFSの入退場記録へ進みます。
ABC251 Fで作る二つの全域木
入力は、頂点数N、辺数Mの単純かつ連結な無向グラフです。単純グラフなので自己ループと同じ二頂点を結ぶ重複辺はなく、連結なので頂点1から全頂点へ到達できます。頂点番号は1からNです。
| 出力 | 構成 | 問題文の条件 |
|---|---|---|
| T1 | 頂点1を根とするDFS木 | T1に含まれない元グラフの辺は、両端がT1で祖先・子孫関係になる |
| T2 | 頂点1を根とするBFS木 | T2に含まれない元グラフの辺で、両端が祖先・子孫関係になるものはない |
| 出力順 | T1の後にT2 | それぞれN−1辺、合計2N−2行 |
制約は2 ≤ N ≤ 2 × 105、N−1 ≤ M ≤ min(2 × 105, N(N−1)/2)です。各木の辺の順序と、辺の両端をどちらから書くかは任意なので、公式サンプルの出力と同じ行順でなくても条件を満たせます。詳しい入出力とサンプルはABC251 Fの公式問題文、構成の方針と証明は公式解説で確認できます。
未訪問頂点への最初の辺を木にする
グラフを探索するとき、各頂点vの隣接頂点をgraph[v]へ並べる隣接リストを使います。無向辺(u, v)を読み込んだら、uのリストにv、vのリストにuを追加します。探索中に頂点を初めて発見した辺だけを保存すれば、根から新しい頂点を一つずつ木へつなげられます。
| 探索 | 次に取り出すもの | 木へ辺を追加する時点 | 得られる見え方 |
|---|---|---|---|
| DFS | 後から積んだ頂点を先に取り出すスタック | 頂点を初めて訪問済みにした時 | 一つの枝を深く進み、行き止まりで戻る |
| BFS | 先に入れた頂点を先に取り出すキュー | 未訪問の隣接頂点をキューへ入れる時 | 根からの距離が近い層から進む |
DFSは同じ頂点がスタックへ候補として複数回積まれることがあります。そのため掲載コードでは、取り出した時点でseen[v]を確認し、まだ訪問していなければ親辺を一度だけ保存します。BFSはキューへ入れる時点でseenを立てるため、同じ頂点を二度キューへ入れません。どちらも、辺を保存する基準は「初めて発見した頂点の親辺」です。
同じ4頂点グラフをDFSとBFSで追う
次の入力はABC251 Fの公式サンプルではありません。探索の違いを追うために、頂点1, 2, 3, 4と、入力順が1−2、1−3、2−3、3−4のグラフを使います。
4 4
1 2
1 3
2 3
3 4DFSでできるT1
- 頂点1を訪問済みにし、隣接リストの順序に従って2と3をスタックへ候補として積みます。後から積んだ2を先に取り出すため、1−2をT1へ追加します。
- 頂点2から未訪問の3を発見し、2−3を追加します。辺1−3のもう一方の端点はすでに候補ですが、3が先に2から訪問済みになるため、1−3は木へ入りません。
- 頂点3から未訪問の4を発見し、3−4を追加します。これでT1は1−2、2−3、3−4です。
T1に含まれない辺1−3は、根1から見て1が3の祖先です。DFSが枝を深く進むため、同じ枝の途中にある頂点同士を結ぶ辺が非木辺として残ります。
BFSでできるT2
- 頂点1をキューへ入れ、1を処理して2と3を順に発見します。1−2と1−3をT2へ追加し、2と3をキューへ入れます。
- 次に2を処理しても、隣接する1と3は訪問済みです。新しい辺は増えません。
- 続いて3を処理し、未訪問の4を発見して3−4を追加します。T2は1−2、1−3、3−4です。
T2に含まれない辺2−3の両端は、根1から同じ距離1にあります。したがって一方が他方の祖先ではありません。同じ入力でも、DFSは1−2−3−4と深く伸び、BFSは距離1の2と3を同じ層へ置くため、保存される辺が変わります。
なぜT1にDFS、T2にBFSを選ぶのか
DFS木では非木辺が祖先と子孫を結ぶ
DFSで頂点uを処理している間に、uと隣接する未訪問頂点vが残っていれば、DFSはその辺からv側へ進んでから、uより上の頂点へ戻ります。したがって、探索が別の枝へ戻った後に、元の枝と新しい枝を結ぶ非木辺が現れることはありません。もし非木辺の両端が互いに祖先でなければ、先に処理した側からもう一方へ進める機会を残したまま戻ったことになり、DFSの探索順と矛盾します。元グラフが無向なので、どちら側を先に見ても同じ議論ができ、すべての非木辺は祖先と子孫を結びます。
BFS木では非木辺が祖先と子孫を結ばない
BFS木で根1から頂点vまでの木の深さをd(v)とします。BFSは距離0の1を処理してから距離1、距離2という順に進み、初めて発見した頂点の深さが元グラフでの最短距離になります。元グラフの辺u−vがあれば、uからvへ一歩進む経路もあるため、|d(u)−d(v)|は1以下です。
非木辺u−vの両端が祖先・子孫関係だと仮定します。異なる頂点なので深さの差は少なくとも1ですが、上の性質から差は1だけです。すると浅い方は深い方の直上の親であり、辺u−vはBFS木にも入るはずです。これは非木辺だったことと矛盾します。ここで、同じ二頂点を結ぶ別の辺が存在しないという単純グラフの条件が必要です。
完全なPythonコード
コードは入力辺を両方向の隣接リストへ登録し、visited配列をリセットしてDFSとBFSをそれぞれ一度ずつ実行します。頂点番号が1始まりなので、配列の長さをN＋1にし、添字0はDFSの根に親がないことを表す仮想的な値としてだけ使います。再帰ではなくスタックを使うため、深さが大きい入力でも再帰の深さに依存しません。
import sys
from collections import deque
def dfs_tree(graph, n):
seen = [False] * (n + 1)
tree = []
stack = [(0, 1)]
while stack:
parent, v = stack.pop()
if seen[v]:
continue
seen[v] = True
if parent != 0:
tree.append((parent, v))
for u in reversed(graph[v]):
if not seen[u]:
stack.append((v, u))
return tree
def bfs_tree(graph, n):
seen = [False] * (n + 1)
tree = []
queue = deque([1])
seen[1] = True
while queue:
v = queue.popleft()
for u in graph[v]:
if seen[u]:
continue
seen[u] = True
tree.append((v, u))
queue.append(u)
return tree
def main():
input = sys.stdin.buffer.readline
n, m = map(int, input().split())
graph = [[] for _ in range(n + 1)]
for _ in range(m):
u, v = map(int, input().split())
graph[u].append(v)
graph[v].append(u)
t1 = dfs_tree(graph, n)
t2 = bfs_tree(graph, n)
sys.stdout.write('\n'.join(f'{u} {v}' for u, v in t1 + t2))
if __name__ == '__main__':
main()コードの処理を問題条件へ対応させる
dfs_treeではスタックに親と頂点の組を入れます。頂点を初めて取り出した時だけseen[v]を立て、根以外ならその親辺をT1へ追加します。reversedは隣接リストの順を保ったままスタックの後入れ先出しへ合わせるためのもので、出力順は問題上の必須条件ではありません。
bfs_treeでは根1を先に訪問済みにしてキューへ入れます。未訪問の隣接頂点を見つけた瞬間に訪問済みとし、親辺をT2へ追加してキューの末尾へ入れます。この順序により、別の頂点から同じ頂点を見ても二本目の親辺を追加しません。
mainはT1の全辺を出力した後、T2の全辺を出力します。t1 + t2の順序が、そのまま問題の2N−2行の区切りになります。
正しさ、計算量、境界を確認する
二つとも全域木になる理由
連結性により、頂点1からのDFSとBFSはすべてのN頂点を訪問します。根1を除く各頂点は、最初に発見された時にちょうど一本の親辺を追加されるので、各木の辺数はN−1です。追加される辺は、すでに探索で到達した頂点から新しい頂点へつながるため、根から全頂点へ届きます。新しい頂点を一度だけ接続する構造なので閉路も生じず、T1とT2はともに全域木です。
計算量
隣接リストの構築では各入力辺を二方向へ登録します。DFSとBFSは、訪問済みの各頂点について隣接リストを調べ、各入力辺を定数回だけ確認します。したがって全体の時間計算量はO(N + M)です。隣接リスト、訪問済み配列、二つの木、探索用のスタックまたはキューを合わせた追加メモリもO(N + M)です。
制約から外れる入力を混ぜない
- 連結でないグラフでは未訪問頂点が残り、各木がN−1辺になる保証がありません。このコードはABC251 Fの連結条件のもとで使います。
- 単純グラフでない多重辺を許すと、BFS木に一方の同じ端点の辺が入った後、別の平行辺が非木辺として残る場合があります。BFSの祖先関係の証明をそのまま適用しないでください。
- 最小境界のN=2、M=1では、唯一の辺がT1とT2へ一本ずつ入り、合計2N−2行になります。
- 公式出力は一意ではありません。サンプルの出力とバイト単位で比較せず、次の順に構造を検証します。まず最初のN−1行をT1、続くN−1行をT2として分けます。次に各辺が入力グラフGに存在することを確認します。各ブロックは根1から走査し、全頂点へ一度ずつ到達して閉路がない木になっていることを確認します。この確認は、親を記録する走査でもDSUでも構いません。その走査で親と深さを作り、必要ならDFSの入出時刻も記録して、どちらの頂点が他方の祖先かを判定できるようにします。最後に、入力グラフGから各木の辺を除いた全非木辺を列挙します。T1では列挙したすべての辺について両端の一方が他方の祖先・子孫であることを確認し、T2ではすべての非木辺について祖先・子孫関係にならないことを確認します。
次の練習は、保存する情報を一つ変える
ABC251 Fで「初めて発見した親辺」を保存できたら、次は同じ探索を別の出力目的へ置き換えます。どちらもABC251 Fと同じ二本の全域木を出力する問題ではありません。何を保存し、何を答えにするかを問題文から先に切り分けます。
ABC168 D：BFS木を最短距離の道しるべへ
ABC168 D .. (Double Dots)では、部屋1以外の各部屋から部屋1へ最小回数で戻るための道しるべを構成します。ABC251 FのBFSと同じく、根からの距離が一段ずつ増える頂点を探索しますが、出力するのは木の全辺ではなく、各部屋の親となる部屋です。公式解説の解説PDFで、深さd＋1の部屋から深さdの部屋へ戻る理由を確認し、seenと親配列の役割を対応させます。
ABC213 D：DFS木を入退場の訪問列へ
ABC213 D Takahashi Tourでは、連結な木を都市1から出発し、未訪問の隣接都市があれば最小番号を選び、なければ直前の都市へ戻る旅の列を出力します。ABC251 FのDFS木で保存した「入る時の辺」だけでなく、戻る時の頂点も記録する点が違います。公式解説のDFSとEuler tourの説明を読み、木の構造と入退場の記録を分けて確かめます。
ABC251 Fへ戻って実装を点検するときは、問題が求めているものを「初回発見辺の集合」「最短距離の親」「入退場を含む訪問列」のどれとして保存するのかを一行で書いてからコードを追うと、DFSとBFSの使い分けを別の問題にも移せます。
