基本情報技術者試験「グラフ」の問題
有向グラフを次の辺リストで与える（u → v は u から v への辺）。
1→2, 1→3, 2→4, 5→1
次の手続 reachCount は、始点 s から有向辺をたどって到達できるノードの総数（s 自身を含む）を返す。スタックを用いた深さ優先で探索する。reachCount(1) を実行したとき、戻り値はどれか。
○整数型: reachCount(整数型: s)
stack ← 空のスタック
visited[s] ← true
push(s)
整数型: cnt ← 1
while (stack が空でない)
整数型: u ← pop()
整数型: v
for (v を 1 から 5 まで 1 ずつ増やす)
if (辺 u→v が存在 かつ visited[v] が false)
visited[v] ← true
cnt ← cnt + 1
push(v)
endif
endfor
endwhile
return cntア到達 4 個
イ全 5 個
ウ始点のみ 1 個
エ2 個
正解
ア．到達 4 個
1 から有向辺をたどると 2,3 へ、さらに 2 から 4 へ到達する。到達集合は {1,2,3,4} の 4 個であり、5 は 1 へ向かう辺しか持たず到達できないため、cnt=4 となり アが正しい。
?選択肢ごとの解説
ア ○1 から有向辺をたどると 2,3 へ、さらに 2 から 4 へ到達する。到達集合は {1,2,3,4} の 4 個であり、5 は 1 へ向かう辺しか持たず到達できないため、cnt=4 となり アが正しい。
イ ×全ノード数 5 をそのまま答えた、有向辺の向きを無視して 5→1 を逆向きにたどれると誤認した誤りである。
ウ ×始点 1 だけを数えて隣接ノードへの探索を行わなかった、ループ未実行の誤りである。
エ ×1 の直接の隣接 2,3 のうち 1 つ分しか進めず 2 個とした、間接到達 4 と分岐を取りこぼした誤りである。
✎くわしく
有向グラフの到達可能性は辺の向きに厳密に従う。入ってくる辺（5→1）は始点からの到達には寄与せず、出ていく辺だけをたどる点が無向グラフとの違いである。
✓本番での押さえどころ
試験のコツ
矢印の向きに沿ってのみ進み、始点へ入る辺は探索に使わないことを徹底する。
覚え方
『有向は一方通行、向きに逆らわない』と覚える。
よくある誤り
有向辺を無向と勘違いし、5→1 を逆にたどって 5 まで数えるミスが多い。
アルゴリズムとプログラミングの他の問題
次の擬似言語で表される手続 sumOdd を、引数として要素数 5 の整数型の配列 {12, 125, 1008,…次の擬似言語は、整数型の配列 arr に対して隣接交換を行う手続の一部であり、外側ループの 1 回目（1…次の擬似言語は昇順に整列された配列 arr に対する二分探索の手続である。arr = {2, 4, 6, 8, 10,…次の擬似言語で表される再帰手続 f を、引数 n = 20 で呼び出したとき、戻り値として返される値はどれか。
```…単方向連結リストの各ノードはメンバ val（整数）と next（次ノードへの参照。なければ NULL）をもつ。先頭ノード…スタックに対する push（積む）と…
この問題を、AIの8-ways解説つきで。
無料ではじめる →基本情報技術者試験の演習を、一問ごとに「なぜ」まで。まずは無料で。
ukamiru 過去問 · 基本情報技術者試験 · fe-b-algo-0149