Day 003-Q5 | DFS基礎

問題

N頂点 M辺の無向グラフがある。頂点は 1〜N で番号付け。頂点 1 から到達できる頂点の数（頂点1自身を含む）を出力せよ。

入力形式

N M
u_1 v_1
...
u_M v_M

制約

$1 \le N \le 1000$

$0 \le M \le 5000$

自己ループ・多重辺なし

入出力例

入力例 1

出力例 1

入力例 2

出力例 2

ヒント (段階的開示)

ヒント1: 方向性

グラフをたどって「行けるところを全部訪れる」アルゴリズムが DFS。スタックまたは再帰で実装。

ヒント2: アプローチ

隣接リスト → visited 配列 → 頂点1からDFS → 訪問済み数を数える。

ヒント3: 誘導

def dfs(v):
    visited[v] = True
    for nv in graph[v]:
        if not visited[nv]:
            dfs(nv)
dfs(1)
print(sum(visited))

模範解答 (Python)

import sys
from collections import defaultdict

sys.setrecursionlimit(10000)

input_data = sys.stdin.read().split()
idx = 0
N = int(input_data[idx]); idx += 1
M = int(input_data[idx]); idx += 1

graph = defaultdict(list)
for _ in range(M):
    u = int(input_data[idx]); idx += 1
    v = int(input_data[idx]); idx += 1
    graph[u].append(v)
    graph[v].append(u)

visited = [False] * (N + 1)

def dfs(v):
    visited[v] = True
    for nv in graph[v]:
        if not visited[nv]:
            dfs(nv)

dfs(1)
print(sum(visited))

Step-by-Step 解説

1グラフの表現（隣接リスト）
graph[v] = 頂点 v に隣接する頂点のリスト。無向なので両方向追加。

2DFS の仕組み
「行けるだけ深く進み、行き詰まったら戻る」。visited で同じ頂点の2度訪問を防ぐ。

3再帰制限
Pythonのデフォルトは1000。N=1000 の一直線パスで setrecursionlimit で増やす。

4結果集計
sum(visited) で True(=1) の個数を取得。

よくあるミス

ミス	原因	正しい書き方
RecursionError	デフォルト上限1000	`sys.setrecursionlimit`
無向グラフで片方向のみ	逆辺を追加していない	両方向追加
`sum(visited)` が N+1 個	0/1-indexed混同	`[False]*(N+1)` で 1-indexed

Day 003-Q5 — DFS（深さ優先探索）基礎

問題