この問題は BFS により解くことができます。

人を頂点、連絡手段を辺としたグラフを考えると、人 \(S\) に対応する頂点から最も遠い頂点までの距離が答えとなります。よって、人 \(S\) に対応する頂点から各頂点までの距離が分かればよく、BFS により求めることができます。

実装例 (C++)

#include<bits/stdc++.h>
using namespace std;

int main(){
  int n, m, s;
  cin >> n >> m >> s;
  s--;
  vector<vector<int>>G(n);
  for(int i=0; i<m; i++){
    int u, v;
    cin >> u >> v;
    u--, v--;
    G[u].push_back(v);
  }

  const int INF = (int)1e9;
  vector<int> dist(n, INF);
  queue<int> q({s});
  dist[s] = 0;
  while(q.size() > 0){
    int v = q.front(); q.pop();
    for(auto vv: G[v]){
      if(dist[vv] == INF){
        dist[vv] = dist[v] + 1;
        q.push(vv);
      }
    }
  }

  int ans = *max_element(dist.begin(), dist.end());
  if(ans == INF){
    cout << -1 << endl;
  }else{
    cout << ans << endl;
  }
}

実装例 (Python)

N, M, S = map(int, input().split())
S -= 1
G = [[] for _ in range(N)]
for _ in range(M):
  U, V = map(int, input().split())
  U -= 1
  V -= 1
  G[U].append(V)

INF = 10**9
dist = [INF] * N
q = [S]
dist[S] = 0
for v in q:
  for vv in G[v]:
    if dist[vv] == INF:
      dist[vv] = dist[v] + 1
      q.append(vv)

ans = max(dist)
if ans == INF:
  print(-1)
else:
  print(ans)