UVa - 627 - The Net

1. #include <bits/stdc++.h>
2. #define mem(n) memset(n, 0, sizeof(n))
3. #define memm(n) memset(n, -1, sizeof(n))
4. using namespace std;
5.  
6. vector <int> net[303];
7. int vis[303], path[303];
8.  
9. void print_path(int v, int u){
10.     int p = path[v];
11.     if(p != u)print_path(p, u);
12.     cout << p << " ";
13. }
14.  
15. void BFS(int src, int dest){
16.     queue <int> Q;
17.     Q.push(src);
18.     vis[src] = 1;
19.     while(!Q.empty()){
20.         int u = Q.front();
21.         Q.pop();
22.         int sz = net[u].size();
23.         for(int i = 0; i < sz; i++){
24.             int v = net[u][i];
25.             if(!vis[v]){
26.                 vis[v] = 1;
27.                 Q.push(v);
28.                 path[v] = u;
29.             }
30.         }
31.     }
32.     if(path[dest] == -1)puts("connection impossible");
33.     else print_path(dest, src), cout << dest << endl;
34. }
35.  
36. int main(){
37.     int test, num, ind, x, y;
38.     int n, m, k, start, endd;
39.     string routes;
40.     while(cin >> n){
41.         for(int i = 1; i <= n; i++){
42.             cin >> routes; num = 0;
43.             int sz = routes.size();
44.             for(int j = 0; j < sz; j++){
45.                 if(routes[j] == '-')ind = num, num = 0;
46.                 else if(routes[j] == ',')net[ind].push_back(num), num = 0;
47.                 else num = (num*10) + (routes[j]-'0');
48.             }
49.             if(num)net[ind].push_back(num);
50.         }
51.         cin >> m;
52.         puts("-----");
53.         for(int i = 1; i <= m; i++){
54.             cin >> start >> endd;
55.             memm(path), mem(vis);
56.             BFS(start, endd);
57.         }
58.         for(int i = 1; i <= n; i++)net[i].clear();
59.     }
60.     return 0;
61. }