Advertisement
codecstasy

UVa 336 - A node too far

Apr 21st, 2021
103
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.51 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define fora(i,n) for(int i=0 ; i<n ; i++)
  3. #define pb(x) push_back(x)
  4. using namespace std;
  5.  
  6. unordered_map <int, vector <int> > adj;
  7. //vector <int> level(35),vis(35);
  8. int level[35],vis[35];
  9. int cs;
  10.  
  11. int bfs(int src,int ttl) {
  12.     int ans=0;
  13.     vis[src]=1;
  14.     level[src]=0;
  15.     queue <int> q;
  16.     q.push(src);
  17.     while(!q.empty()) {
  18.         int u=q.front();q.pop();
  19.         //unordered_map <int, vector <int> > :: iterator &v;
  20.         for(auto v : adj[u]) {
  21.             if(vis[v]==0) {
  22.                 //nd++;
  23.                 vis[v]=1;
  24.                 level[v]=level[u]+1;
  25.                 //cout << (v) << ": " <<  level[v] << endl;
  26.                 if(level[v]>ttl) ans++;
  27.                 q.push(v);
  28.             }
  29.         }
  30.     }
  31.     return ans;
  32. }
  33.  
  34. int main() {
  35.     cs=1;
  36.     while(1) {
  37.         int e;
  38.         cin >> e;
  39.         if(e==0) break;
  40.         fora(i,e) {
  41.             int x,y;
  42.             cin >> x >> y;
  43.             adj[x].pb(y);
  44.             adj[y].pb(x);
  45.         }
  46.         for( ; ; cs++) {
  47.             int src,ttl;
  48.             cin >> src >> ttl;
  49.             memset(vis,0,sizeof vis);
  50.             memset(level,-1,sizeof level);
  51.             if(src==0 && ttl==0) {
  52.                 cs--;
  53.                 break;
  54.             }
  55.             int ans=bfs(src,ttl);
  56.             //cout << bfs(src,ttl) << endl;
  57.             printf("Case %d: %d nodes not reachable from node %d with TTL = %d.\n",cs,ans,src,ttl);
  58.         }
  59.         adj.clear();
  60.     }
  61.     return 0;
  62. }
  63.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement