Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- #define mx 1000000
- bool vis[mx];
- int n,e,cnt;
- vector<int>v[mx];
- int dis[mx];
- map<int,int>m;
- map<int,int>::iterator it;
- int bfs(int sn,int z)
- {
- int i,j;
- for(it=m.begin();it!=m.end();it++){
- vis[it->first]=false;
- dis[it->first]=5000000;
- }
- dis[sn]=0;
- vis[sn]=true;
- queue<int >q;
- q.push(sn);
- while(!q.empty()){
- int x=q.front();
- q.pop();
- for(i=0;i<v[x].size();i++){
- if(vis[v[x][i]]==false){
- dis[v[x][i]]=dis[x]+1;
- vis[v[x][i]]=true;
- q.push(v[x][i]);
- }
- }
- }
- return cnt;
- }
- int main()
- {
- int i,j,a,b,p,k=0,l=0,c=0;
- while(1){
- p=0;
- cin>>e;
- if(e==0) break;
- for(i=0;i<e;i++){
- int n1,n2;
- cin>>n1>>n2;
- l=m[n1]++;
- if(l==0) p++;
- k=m[n2]++;
- if(k==0) p++;
- v[n1].push_back(n2);
- v[n2].push_back(n1);
- }
- while(1){
- c++;
- cnt=0;
- scanf("%d%d",&a,&b);
- if(a==0 && b==0) break;
- bfs(a,p);
- for(it=m.begin();it!=m.end();it++){
- if(dis[it->first]>b) cnt++;
- }
- cout<<"Case "<<c<<": "<<cnt<<" nodes not reachable from node "<<a<<" with TTL = "<<b<<"."<<endl;
- }
- for(it=m.begin();it!=m.end();it++){
- v[it->first].clear();
- }
- m.clear();
- cout<<endl;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement