#include<cstdio>
#include<cstring>
#include<map>
#include<queue>
#include<iostream>
using namespace std;
map<int,int>mymap;
queue<int>Q;
int color[50],level[50],mat[50][50];
int connection,i,a,b,tag,start,TTL,tc=0,counter,u;
int main()
{
while(cin>>connection)
{
if(connection==0)
{
break;
}
tag=0;
for(i=1; i<=connection; i++)
{
cin>>a>>b;
if(!mymap[a])
{
mymap[a]=++tag;
}
if(!mymap[b])
{
mymap[b]=++tag;
}
mat[mymap[a]][mymap[b]]=1;
mat[mymap[b]][mymap[a]]=1;
}
for(;;)
{
cin>>start>>TTL;
if(start==0 && TTL==0)
{
break;
}
if(!mymap[start])
{
printf("Case %d: %d nodes not reachable from node %d with TTL = %d.\n",++tc,tag,start,TTL);
continue;
}
Q.push(mymap[start]);
color[mymap[start]]=1;
while(!Q.empty())
{
u=Q.front();
for(i=1; i<=tag; i++)
{
if(mat[u][i]==1 && color[i]!=1)
{
color[i]=1;
level[i]=level[u]+1;
Q.push(i);
}
}
Q.pop();
}
counter=0;
for(i=1; i<=tag; i++)
{
if(level[i]>TTL||color[i]==0)
{
counter++;
}
}
printf("Case %d: %d nodes not reachable from node %d with TTL = %d.\n",++tc,counter,start,TTL);
memset(level,0,sizeof(level));
memset(color,0,sizeof(color));
}
memset(level,0,sizeof(level));
memset(mat,0,sizeof(mat));
memset(color,0,sizeof(color));
mymap.clear();
}
return 0;
}
#include<cstring>
#include<map>
#include<queue>
#include<iostream>
using namespace std;
map<int,int>mymap;
queue<int>Q;
int color[50],level[50],mat[50][50];
int connection,i,a,b,tag,start,TTL,tc=0,counter,u;
int main()
{
while(cin>>connection)
{
if(connection==0)
{
break;
}
tag=0;
for(i=1; i<=connection; i++)
{
cin>>a>>b;
if(!mymap[a])
{
mymap[a]=++tag;
}
if(!mymap[b])
{
mymap[b]=++tag;
}
mat[mymap[a]][mymap[b]]=1;
mat[mymap[b]][mymap[a]]=1;
}
for(;;)
{
cin>>start>>TTL;
if(start==0 && TTL==0)
{
break;
}
if(!mymap[start])
{
printf("Case %d: %d nodes not reachable from node %d with TTL = %d.\n",++tc,tag,start,TTL);
continue;
}
Q.push(mymap[start]);
color[mymap[start]]=1;
while(!Q.empty())
{
u=Q.front();
for(i=1; i<=tag; i++)
{
if(mat[u][i]==1 && color[i]!=1)
{
color[i]=1;
level[i]=level[u]+1;
Q.push(i);
}
}
Q.pop();
}
counter=0;
for(i=1; i<=tag; i++)
{
if(level[i]>TTL||color[i]==0)
{
counter++;
}
}
printf("Case %d: %d nodes not reachable from node %d with TTL = %d.\n",++tc,counter,start,TTL);
memset(level,0,sizeof(level));
memset(color,0,sizeof(color));
}
memset(level,0,sizeof(level));
memset(mat,0,sizeof(mat));
memset(color,0,sizeof(color));
mymap.clear();
}
return 0;
}
0 comments: (+add yours?)
Post a Comment