#include<bits/stdc++.h>
using namespace std;
int main()
{
int edges,cas=1;
while(cin>>edges)
{
if(edges==0)
break;
vector<long long int>nodes[100000];
map<long long ,int>difference;
difference.clear();
int i,j,a,b,num=0;
for(i=0;i<edges;i++)
{
cin>>a>>b;
nodes[a].push_back(b);
nodes[b].push_back(a);
if(difference[a]!=1)
{
difference[a]=1;
num++;
}
if(difference[b]!=1)
{
difference[b]=1;
num++;
}
}
map<long long ,int>visited;
map<long long ,int>level;
visited.clear();
level.clear();
int start,ttl;
int number;
queue<long long int>q;
//int c=0;
while(cin>>start>>ttl)
{
if(start==0 && ttl==0)
break;
number=0;
visited.clear();
visited[start]=1;
level[start]=0;
q.push(start);
while(!q.empty())
{
int front=q.front();
q.pop();
int l=nodes[front].size();
for(i=0;i<l;i++)
{
if(visited[nodes[front][i]]!=1)
{
level[nodes[front][i]]=level[front]+1;
if(level[nodes[front][i]]>ttl)
{
break;
}
number++;
visited[nodes[front][i]]=1;
q.push(nodes[front][i]);
}
}
//q.pop();
}
printf("Case %d: %d nodes not reachable from node %d with TTL = %d.\n",cas,num-number-1,start,ttl);
cas++;
}
}
return 0;
}
using namespace std;
int main()
{
int edges,cas=1;
while(cin>>edges)
{
if(edges==0)
break;
vector<long long int>nodes[100000];
map<long long ,int>difference;
difference.clear();
int i,j,a,b,num=0;
for(i=0;i<edges;i++)
{
cin>>a>>b;
nodes[a].push_back(b);
nodes[b].push_back(a);
if(difference[a]!=1)
{
difference[a]=1;
num++;
}
if(difference[b]!=1)
{
difference[b]=1;
num++;
}
}
map<long long ,int>visited;
map<long long ,int>level;
visited.clear();
level.clear();
int start,ttl;
int number;
queue<long long int>q;
//int c=0;
while(cin>>start>>ttl)
{
if(start==0 && ttl==0)
break;
number=0;
visited.clear();
visited[start]=1;
level[start]=0;
q.push(start);
while(!q.empty())
{
int front=q.front();
q.pop();
int l=nodes[front].size();
for(i=0;i<l;i++)
{
if(visited[nodes[front][i]]!=1)
{
level[nodes[front][i]]=level[front]+1;
if(level[nodes[front][i]]>ttl)
{
break;
}
number++;
visited[nodes[front][i]]=1;
q.push(nodes[front][i]);
}
}
//q.pop();
}
printf("Case %d: %d nodes not reachable from node %d with TTL = %d.\n",cas,num-number-1,start,ttl);
cas++;
}
}
return 0;
}
No comments:
Post a Comment