Advertisement
shamiul93

A Node Too Far

Oct 9th, 2016
164
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.20 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define ll long long int
  6. #define pb push_back
  7. #define initial(arr,N)  memset(arr,N,sizeof(arr))
  8.  
  9. vector<ll> Vector[300];
  10. queue<ll> Queue;
  11. map<ll, ll> Map;
  12.  
  13.  
  14. ll assigned ;
  15.  
  16. void Input(ll NC);
  17. ll BFS(ll SourceNode,ll TTL);
  18.  
  19.  
  20. void Input(ll NC)
  21. {
  22.     ll i, j;
  23.     assigned = 0 ;
  24.     for (i = 0; i < NC; i++)
  25.     {
  26.         ll First, Second ;
  27.         cin >> First>> Second;
  28.  
  29.         if (Map.find(First) == Map.end())
  30.         {
  31.             Map[First] = assigned;
  32.             assigned++;
  33.  
  34.         }
  35.         if (Map.find(Second) == Map.end())
  36.         {
  37.             Map[Second] = assigned;
  38.             assigned++;
  39.         }
  40.         Vector[Map[First]].pb(Map[Second]);
  41.         Vector[Map[Second]].pb(Map[First]);
  42.     }
  43.  
  44.     return;
  45. }
  46.  
  47.  
  48. ll BFS(ll SourceNode,ll TTL)
  49. {
  50.     ll i, j , Source;
  51.     ll Visited[300] = {};
  52.     ll Level[300] ;
  53.     initial(Level,-1);
  54.  
  55.     Source = Map[SourceNode];
  56.  
  57.     Queue.push(Source);
  58.     Level[Source] = 0;
  59.     Visited[Source] = 1 ;
  60.     while (!Queue.empty())
  61.     {
  62.         ll Node;
  63.         Node = Queue.front();
  64.         Queue.pop();
  65.  
  66.         for (i = 0; i < Vector[Node].size(); i++)
  67.         {
  68.             if (Visited[Vector[Node][i]]==0)
  69.             {
  70.                 Visited[Vector[Node][i]] = 1;
  71.                 Level[Vector[Node][i]] = Level[Node] + 1  ;
  72.                 Queue.push(Vector[Node][i]);
  73.             }
  74.         }
  75.     }
  76.  
  77.     ll counter = 0;
  78.     for (i = 0; i < assigned; i++)
  79.     {
  80.         if (Level[i]>=0 && Level[i]<=TTL)
  81.         {
  82.             counter++;
  83.         }
  84.     }
  85.  
  86.     return assigned - counter;
  87.  
  88. }
  89.  
  90. int main()
  91. {
  92.     //freopen("in.txt","r",stdin);
  93.     ll NC, Unreached , SourceNode , TTL, t=0;
  94.     while ((cin >> NC) && NC)
  95.     {
  96.         Input(NC);
  97.         while ((cin >> SourceNode >> TTL) && (SourceNode || TTL))
  98.         {
  99.             t++;
  100.             Unreached = BFS(SourceNode, TTL);
  101.             printf("Case %lld: %lld nodes not reachable from node %lld with TTL = %lld.\n", t, Unreached, SourceNode, TTL);
  102.         }
  103.         for(int i=0 ; i<300 ; i++)
  104.         {
  105.             Vector[i].clear();
  106.         }
  107.         Map.clear();
  108.     }
  109.     return 0;
  110. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement