POJ 2781 - The mysterious X network

http://poj.org/problem?id=2781

概要

N 人について誰と誰が camarade かの関係が与えられる． camarade の関係は対称的である．

c1 から c2 まで camarade の関係にある人同士のみで伝えていったとき，仲介する必要のある人数の最小値を答える．

この camarade 関係による X network は連結であるとする．

制約

• 1 <= N <= 10^5

解法

BFS するだけ．

 1 #include <cstdio>
 2 #include <vector>
 3 #include <queue>
 4 using namespace std;
 5 
 6 int bfs(const vector<vector<int> >& g, int start, int goal)
 7 {
 8   queue<pair<int,int> > q;
 9   q.push(make_pair(start, 0));
10   vector<bool> visited(g.size(), false);
11   visited[start] = true;
12   while (!q.empty()) {
13     const pair<int,int> p = q.front();
14     q.pop();
15     const int n = p.first;
16     const int d = p.second;
17     if (n == goal) {
18       return d-1;
19     }
20     for (vector<int>::const_iterator it(g[n].begin()); it != g[n].end(); ++it) {
21       if (!visited[*it]) {
22         visited[*it] = true;
23         q.push(make_pair(*it, d+1));
24       }
25     }
26   }
27   return -1;
28 }
29 
30 int main()
31 {
32   int N;
33   scanf("%d", &N);
34   vector<vector<int> > g(N);
35   for (int i = 0; i < N; i++) {
36     int c, nc;
37     scanf("%d %d", &c, &nc);
38     g[c].resize(nc);
39     for (int j = 0; j < nc; j++) {
40       scanf("%d", &g[c][j]);
41     }
42   }
43   int c1, c2;
44   scanf("%d %d", &c1, &c2);
45 
46   printf("%d %d %d\n", c1, c2, bfs(g, c1, c2));
47   return 0;
48 }