Lightoj 1174 - Commandos

http://lightoj.com/volume_showproblem.php?problem=1174

1. #include <bits/stdc++.h>
2. using namespace std;
3. #define N 105
4. #define dbg printf("comes here\n");
5. vector<int> adj[N];
6. int n, m;
7. bool visited[N];
8. int dis1[N], dis2[N];
9. void clear(){
10.     for(int i = 0; i <=n; i++){
11.         adj[i].clear();
12.         dis1[i] = dis2[i] = INT_MAX;
13.     }
14. }
15. void bfs1(int source){
16.     for(int i = 0; i <n; i++) visited[i] = false;
17.     list<int>q;
18.     q.push_back(source);
19.     visited[source]= true;
20.     dis1[source] = 0;
21.     while(!q.empty()){
22.         int from = q.front();
23.         visited[from] = true;
24.         q.pop_front();
25.         for(int i = 0; i <adj[from].size(); i++){
26.             int to = adj[from][i];
27.             if(visited[to]) continue;
28.             visited[to] = true;
29.             q.push_back(to);
30.             dis1[to] = dis1[from] + 1;
31.         }
32.     }
33. }
34.  
35. void bfs2(int source){
36.     for(int i = 0; i <n; i++) visited[i] = false;
37.     list<int>q;
38.     q.push_back(source);
39.     visited[source]= true;
40.     dis2[source] = 0;
41.     while(!q.empty()){
42.         int from = q.front();
43.         q.pop_front();
44.         for(int i = 0; i <adj[from].size(); i++){
45.             int to = adj[from][i];
46.             if(visited[to]) continue;
47.             visited[to] = true;
48.             q.push_back(to);
49.             dis2[to] = dis2[from] + 1;
50.         }
51.     }
52. }
53.  
54. int main(){
55.     int ts;
56.     scanf("%d", &ts);
57.     for(int c = 1; c <= ts; c++){
58.     clear();
59.     scanf("%d%d", &n, &m);
60.     for(int i = 0; i <m; i++){
61.         int a, b;
62.         scanf("%d%d", &a, &b);
63.         //if(a == b) continue;
64.         adj[a].push_back(b);
65.         adj[b].push_back(a);
66.     }
67.     int s, t;
68.     scanf("%d%d", &s, &t);
69.     bfs1(s);
70.     bfs2(t);
71.     /*
72.     for(int i = 0; i <n; i++) cout<<dis1[i]<<" ";
73.     cout<<endl;
74.     for(int i = 0; i <n; i++) cout<<dis2[i]<<" ";
75.     cout<<endl;
76.     */
77.     int di = 0;
78.     for(int i = 0; i <n; i++) di = max(di,dis1[i] + dis2[i]);
79.     printf("Case %d: %d\n", c, di);
80.     }
81.     return 0;
82. }