Advertisement
NAbdulla

A node too far

May 8th, 2015
288
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.90 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <vector>
  4. #include <queue>
  5. #include <set>
  6.  
  7. using namespace std;
  8.  
  9. int main()
  10. {
  11.     long long NC, i, j, k, u, v, nodes, maxi, reach, kase = 1, ttl, lev;
  12.     vector<long long> graph[100100];
  13.     set<long long> s;
  14.     while((scanf("%lld", &NC) == 1) && NC){
  15.         maxi = 0;
  16.         for(i = 0; i < NC; i++){
  17.             scanf("%lld %lld", &u, &v);
  18.             graph[u].push_back(v);
  19.             graph[v].push_back(u);
  20.             if(maxi < max(u, v))maxi = max(u, v);
  21.             s.insert(u);
  22.             s.insert(v);
  23.             //printf("%d\n", s.size());
  24.         }
  25.         nodes = s.size();
  26.  
  27.         while(scanf("%lld %lld", &u, &v) == 2){
  28.             if(u == 0 && v == 0)break;
  29.  
  30.             ttl = v;
  31.             queue<int>Q[35];
  32.             lev = 0;
  33.             Q[lev].push(u);
  34.             int visited[100100] = {0};
  35.             visited[u] = 1;
  36.             reach = 1;
  37.             while(ttl){
  38.                 while(!Q[lev].empty()){
  39.                     k = Q[lev].front();
  40.                     Q[lev].pop();
  41.                     int si = graph[k].size();
  42.                     for(i = 0; i < si; i++){
  43.                         j = graph[k][i];
  44.                         if(visited[j] == 0){
  45.                             reach++;
  46.                             visited[j] = 1;
  47.                             Q[lev+1].push(j);
  48.                         }
  49.                     }
  50.                 }
  51.                 lev++;
  52.                 ttl--;
  53.             }
  54.             printf("Case %lld: %lld nodes not reachable from node %lld with TTL = %lld.\n", kase++, nodes-reach, u, v);
  55.             for(i = 0; i <= lev; i++){
  56.                 while(!Q[i].empty())Q[i].pop();
  57.             }
  58.         }
  59.         s.erase(s.begin(), s.end());
  60.  
  61.         for(i = 0; i <= maxi; i++){
  62.             graph[i].erase(graph[i].begin(), graph[i].end());
  63.         }
  64.     }
  65.     return 0;
  66. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement