Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- Problem Id : 336 - A Node Too Far
- Author : Kaidul Islam
- Khulna University of Engr. & Tech.
- */
- #include<iostream>
- #include<algorithm>
- #include<vector>
- #include<cstring>
- #include<queue>
- #include<stack>
- #include<set>
- #include <fstream>
- #define Max 100000
- #define pb push_back
- #define READ(f) freopen(f, "r", stdin)
- #define WRITE(f) freopen(f, "w", stdout)
- using namespace std;
- vector<int>adj[Max];
- int main()
- {
- //READ("in.txt");
- queue<int>q;
- set<int>s;
- int caseNo=1,e,x,y,src,ttl;
- int dis[Max+1],visited[Max];
- memset(visited, 0,sizeof(visited));
- label:
- while(cin>>e)
- {
- for(int i=0;i<Max;i++) adj[i].clear();
- q=queue<int>();
- s.clear();
- if(e==0) return 0;
- else
- {
- for(int i=0;i<e;i++)
- {
- cin>>x>>y;
- adj[x].pb(y);
- adj[y].pb(x);
- s.insert(x);
- s.insert(y);
- }
- while(cin>>src>>ttl)
- {
- if(src==0 && ttl==0) goto label;
- else
- {
- int count=1,z=0;
- q.push(src);
- dis[src]=0;
- visited[src]=1;
- while(!q.empty())
- {
- int pop=q.front();
- for(int i=0;i<(int)adj[pop].size();i++)
- {
- int temp=adj[pop][i];
- if(!visited[temp])
- {
- dis[temp]=dis[pop]+1;
- if(dis[temp]>ttl) break;
- q.push(temp);
- visited[temp]=1;
- count++;
- }
- }
- q.pop();
- }
- z=s.size()-count;
- if( z<0 ) z=0;
- cout<<"Case "<<caseNo<<": "<<z
- <<" nodes not reachable from node "
- <<src<<" with TTL = "<<ttl<<".\n";
- caseNo++;
- }
- memset(visited, 0, sizeof(visited));
- }
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement