概要

グラフ上で始点から最大 \(K\) 回の移動で到達できる頂点の数を求める問題です。幅優先探索（BFS）を使って効率的に解くことができます。

考察

問題の言い換え

この問題は、グラフ理論の言葉で言い換えると「始点 \(S\) から距離 \(K\) 以内にある頂点の個数を求める」問題です。ここで「距離」とは、2頂点間の最短経路に含まれる辺の数を指します。

素朴なアプローチの問題点

もし深さ優先探索（DFS）で「\(K\) 回以内の移動で到達できるか」を判定しようとすると、同じ頂点を何度も訪れる可能性があります。例えば、頂点 \(A\) に距離 \(2\) で到達した後、別の経路で距離 \(3\) でも到達してしまい、無駄な探索が発生します。

解決策

幅優先探索（BFS） を使えば、各頂点への最短距離を効率的に求められます。BFSには「始点に近い頂点から順に探索する」という性質があるため、一度訪れた頂点を再び訪れる必要がありません。

アルゴリズム

1. グラフの構築: 接触関係を隣接リストで表現します。

2. BFSの実行:

   • 始点 \(S\) をキューに入れ、距離を \(0\) に設定
   • キューから頂点を取り出し、距離が \(K\) 以下ならカウントを増やす
   • 隣接する未訪問の頂点について、距離を計算してキューに追加

3. 距離 \(K\) 以下の頂点をカウント: BFSの過程で、距離が \(K\) 以下の頂点だけを数えます。

具体例

\(N=5, M=4, S=1, K=2\) で、辺が \((1,2), (2,3), (3,4), (1,5)\) の場合：

    1 --- 2 --- 3 --- 4
    |
    5

• 距離 \(0\): 頂点 \(1\)（始点）
• 距離 \(1\): 頂点 \(2, 5\)（\(1\) の隣接頂点）
• 距離 \(2\): 頂点 \(3\)（\(2\) の隣接頂点）
• 距離 \(3\): 頂点 \(4\)（到達できるが \(K=2\) を超える）

答えは \(4\) 人（頂点 \(1, 2, 3, 5\)）です。

計算量

• 時間計算量: \(O(N + M)\)
  • 各頂点は高々1回キューに追加され、各辺は高々2回（両端点から1回ずつ）調べられます
• 空間計算量: \(O(N + M)\)
  • 隣接リストに \(O(N + M)\)、距離配列とキューに \(O(N)\)

実装のポイント

1. 距離の管理: dist[v] = -1 で未訪問を表し、訪問時に実際の距離を記録します。これにより訪問済み判定と距離管理を1つの配列で行えます。

2. 枝刈り: キューに追加する時点で dist[u] <= K をチェックすることで、\(K\) を超える距離の頂点をキューに入れないようにしています。これにより無駄な探索を防げます。

3. 1-indexed: 頂点番号が \(1\) から \(N\) なので、配列サイズを \(N+1\) にして 1-indexed で扱っています。

4. カウントのタイミング: キューから取り出した時点で距離が \(K\) 以下であることを確認してからカウントしています。

   ソースコード

from collections import deque

def solve():
    N, M, S, K = 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)
    
    # BFSで距離Kまでの頂点を数える
    dist = [-1] * (N + 1)
    dist[S] = 0
    queue = deque([S])
    count = 0
    
    while queue:
        v = queue.popleft()
        if dist[v] > K:
            break
        count += 1
        for u in graph[v]:
            if dist[u] == -1:
                dist[u] = dist[v] + 1
                if dist[u] <= K:
                    queue.append(u)
    
    print(count)

solve()

---

この解説は claude4.5opus によって生成されました。