fork download 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4. map< int, int > visited;
  5.  
  6. void BFS(int s, map< int, vector< int > >G)
  7. {
  8.     queue< int >q;
  9.     q.push(s);
  10.     visited[s] = 0;
  11.     while(!q.empty())
  12.     {
  13.         int top = q.front();
  14.         for(int i=0; i<G[top].size(); i++)
  15.         {
  16.            int n = G[top][i];
  17.            if(!visited.count(n))
  18.            {
  19.                visited[n] = visited[top] + 1;
  20.                q.push(n);
  21.            }
  22.         }
  23.         q.pop();
  24.     }
  25. }
  26.  
  27.  
  28.  
  29. int main()
  30. {
  31.     int edges, cases=0;
  32.     while(scanf("%d",&edges)==1 & edges!=0)
  33.     {
  34.         map< int,vector< int > >G;
  35.         for(int i=0; i<edges; i++)
  36.         {
  37.             int x, y;
  38.             scanf("%d %d", &x, &y);
  39.             G[x].push_back(y);
  40.             G[y].push_back(x);
  41.         }
  42.         int ttl, source;
  43.         while(scanf("%d %d", &source, &ttl)==2)
  44.         {
  45.             if(source==0 && ttl==0) break;
  46.             map< int, int>::iterator it;
  47.             visited.clear();
  48.             BFS(source,G);
  49.             int count=0;
  50.             for(it=visited.begin(); it!=visited.end();++it)
  51.             {
  52.                 if((*it).second>ttl){
  53.                     ++count;
  54.                 }
  55.             }
  56.             //cout<<G.size()<<' '<<visited.size()<<endl;
  57.             count = count + G.size()-visited.size();
  58.             printf("Case %d: %d nodes not reachable from node %d with TTL = %d.\n",++cases,count, source, ttl);
  59.         }
  60.     }
  61.     return 0;
  62. }
  63.  
Success #stdin #stdout 0s 3104KB
comments ()
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/NY4ofJ
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!