Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- map<int, int> visited;
- int BFS(int x, map<int, vector<int> > G)
- {
- queue<int> q;
- q.push(x);
- visited[x]=0;
- while(!q.empty())
- {
- int u=q.front();
- q.pop();
- for(int i=0; i<G[u].size(); i++)
- {
- int d=G[u][i];
- if(!visited.count(d))
- {
- visited[d]=visited[u]+1;
- q.push(d);
- }
- }
- }
- }
- int main()
- {
- int nc, k=0;
- while(cin>>nc)
- {
- if(nc==0)
- break;
- map<int, vector<int> > node;
- int x, y;
- for(int i=0; i<nc; i++)
- {
- cin>>x>>y;
- node[x].push_back(y);
- node[y].push_back(x);
- }
- int s, ttl;
- while(scanf("%d%d", &s, &ttl)==2)
- {
- if(s==0 && ttl==0)
- break;
- map<int, int>::iterator it;
- visited.clear();
- BFS(s, node);
- int cnt=0;
- for(it=visited.begin(); it!=visited.end(); ++it)
- {
- if((*it).second>ttl)
- ++cnt;
- }
- int ans=cnt+node.size()-visited.size();
- printf("Case %d: %d nodes not reachable from node %d with TTL = %d.\n", ++k, ans, s, ttl);
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement