概要

人を頂点、連絡手段を有向辺とみなすと、この問題は「始点 \(S\) から各頂点への最短距離」を求める問題です。
各人がうわさを知る最も早い日は \(S\) からその人までの最短辺数に等しいので、全員に届くなら答えはその最大値、届かない人がいれば \(-1\) です。

考察

うわさは、ある日に知っている人から翌日に隣の人へ伝わります。
つまり、

• 1 日で進めるのはちょうど 1 本の辺
• ある人に最初に届く日は、\(S\) からその人までの「最小の辺数」

となります。

たとえば

• \(S \to A\)
• \(A \to B\)
• \(S \to C\)

という辺があるなら、

• \(S\) は日 \(0\)
• \(A, C\) は日 \(1\)
• \(B\) は日 \(2\)

に知ることになります。
これはまさに、始点 \(S\) からの最短距離そのものです。

重要な気づき

この問題では辺に重みがなく、どの連絡手段も「1 日」で届きます。
したがって、必要なのは 重みなし有向グラフの最短距離 であり、これは BFS（幅優先探索） で求められます。

素朴な方法が厳しい理由

「日ごとに、今知っている人全員から次に広がる人をシミュレーションする」こと自体は考え方としては正しいです。
しかし、実装によっては毎日全頂点や全辺を何度も見てしまい、最悪で非常に遅くなります。

また、DFS（深さ優先探索）では「最初に見つけた経路」が最短とは限らないため、各人が知る最も早い日を正しく求めるのには向きません。

どう解決するか

BFS は「距離 \(0\) の頂点 → 距離 \(1\) の頂点 → 距離 \(2\) の頂点 …」の順に探索します。
そのため、各頂点に最初に到達したときの距離が、その頂点への最短距離になります。

この最短距離を dist[i] とすると、

• dist[i] = -1 ならその人には永遠に届かない
• 全員に届くなら、全員が知る最初の日は \(\max_i dist[i]\)

です。

アルゴリズム

1. 人を頂点、連絡手段を有向辺とした隣接リストを作る。
2. 配列 dist を -1 で初期化する。
3. 始点 S について dist[S] = 0 とし、キューに入れる。
4. BFS を行う。
   • キューから頂点 u を取り出す
   • u から行ける各頂点 v について、まだ未訪問なら
     • dist[v] = dist[u] + 1
     • キューに追加
5. BFS 終了後、
   • dist[i] = -1 の人が 1 人でもいれば -1
   • そうでなければ dist の最大値を出力

なぜこれで正しいか

• うわさは 1 日ごとに 1 本の辺だけ進むので、ある人に届く最短日数は最短辺数です。
• BFS は辺数の少ない順に探索するので、dist[i] は \(S\) から \(i\) への最短辺数になります。
• 全員が知る日は、最後の 1 人に届く日です。したがって答えは最短距離の最大値です。
• 到達できない人がいれば、いつまで経っても全員には広まりません。

計算量

• 時間計算量: \(O(N + M)\)
• 空間計算量: \(O(N + M)\)

実装のポイント

• グラフは 有向グラフ なので、u -> v の向きだけを追加します。

• 最短距離を求めるので、キューを使った BFS を用います。

• dist を -1 で初期化しておくと、

  • 未到達かどうかの判定
  • 到達日数の記録
    を 1 つの配列で兼ねられて便利です。

• 最後に dist を見て、未到達の人がいれば即座に -1 を出力できます。

  ソースコード

import sys
from collections import deque

def main():
    input = sys.stdin.readline
    N, M, S = map(int, input().split())
    graph = [[] for _ in range(N + 1)]
    for _ in range(M):
        u, v = map(int, input().split())
        graph[u].append(v)

    dist = [-1] * (N + 1)
    dist[S] = 0
    q = deque([S])

    while q:
        u = q.popleft()
        du = dist[u]
        for v in graph[u]:
            if dist[v] == -1:
                dist[v] = du + 1
                q.append(v)

    ans = 0
    for i in range(1, N + 1):
        if dist[i] == -1:
            print(-1)
            return
        if dist[i] > ans:
            ans = dist[i]

    print(ans)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.4-high によって生成されました。