Advertisement
Kaidul

336 - A Node Too Far

Aug 18th, 2012
84
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.34 KB | None | 0 0
  1. /*
  2.   Problem Id : 336 - A Node Too Far
  3.   Author     : Kaidul Islam
  4.                Khulna University of Engr. & Tech.
  5. */
  6. #include<iostream>
  7. #include<algorithm>
  8. #include<vector>
  9. #include<cstring>
  10. #include<queue>
  11. #include<stack>
  12. #include<set>
  13. #include <fstream>
  14.  
  15. #define Max 100000
  16. #define pb push_back
  17. #define READ(f) freopen(f, "r", stdin)
  18. #define WRITE(f) freopen(f, "w", stdout)
  19. using namespace std;
  20.  
  21. vector<int>adj[Max];
  22. int main()
  23. {
  24.     //READ("in.txt");
  25.     queue<int>q;
  26.     set<int>s;
  27.     int caseNo=1,e,x,y,src,ttl;
  28.     int dis[Max+1],visited[Max];
  29.     memset(visited, 0,sizeof(visited));
  30.     label:
  31.     while(cin>>e)
  32.     {
  33.         for(int i=0;i<Max;i++) adj[i].clear();
  34.         q=queue<int>();
  35.         s.clear();
  36.         if(e==0) return 0;
  37.         else
  38.         {
  39.             for(int i=0;i<e;i++)
  40.             {
  41.               cin>>x>>y;
  42.               adj[x].pb(y);
  43.               adj[y].pb(x);
  44.               s.insert(x);
  45.               s.insert(y);
  46.  
  47.             }
  48.             while(cin>>src>>ttl)
  49.             {
  50.                 if(src==0 && ttl==0) goto label;
  51.                 else
  52.                 {
  53.                     int count=1,z=0;
  54.                     q.push(src);
  55.                     dis[src]=0;
  56.                     visited[src]=1;
  57.                     while(!q.empty())
  58.                     {
  59.                         int pop=q.front();
  60.                         for(int i=0;i<(int)adj[pop].size();i++)
  61.                         {
  62.                             int temp=adj[pop][i];
  63.                             if(!visited[temp])
  64.                             {
  65.                                 dis[temp]=dis[pop]+1;
  66.                                 if(dis[temp]>ttl) break;
  67.                                 q.push(temp);
  68.                                 visited[temp]=1;
  69.                                 count++;
  70.                             }
  71.                         }
  72.                         q.pop();
  73.                     }
  74.                     z=s.size()-count;
  75.                     if( z<0 ) z=0;
  76.                     cout<<"Case "<<caseNo<<": "<<z
  77.                         <<" nodes not reachable from node "
  78.                         <<src<<" with TTL = "<<ttl<<".\n";
  79.                     caseNo++;
  80.                  }
  81.                  memset(visited, 0, sizeof(visited));
  82.             }
  83.         }
  84.     }
  85.     return 0;
  86. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement