#include <bits/stdc++.h>
#define READ freopen("input.txt","r",stdin);
#define WRITE freopen("output.txt","w",stdout);
using namespace std;
void BFS(int a);
map<int,int>color;
map<int,int>cost;
map<int,int>no_of_node;
map<int,int>::iterator it;
vector<int>v[100000];
int row,col;
queue<int>Q;
int x[]= {-1,+0,+1,+0};
int y[]= {+0,-1,+0,+1};
int main()
{
//READ WRITE
int edge,cas=0;
while(scanf("%d",&edge)==1&&edge!=0)
{
color.clear();
cost.clear();
no_of_node.clear();
for(int i=0;i<100000;i++) v[i].clear();
for(int a=0; a<edge; a++)
{
int x,y;
scanf("%d %d",&x,&y);
v[x].push_back(y);
v[y].push_back(x);
no_of_node[x]++;
no_of_node[y]++;
}
int node,dis;
while(scanf("%d %d",&node,&dis)==2)
{
if(node==0&&dis==0) break;
color.clear();
cost.clear();
int c=0;
BFS(node);
for( it=cost.begin(); it!=cost.end(); it++)
{
if(it->second>dis) c++;
}
c+=no_of_node.size()-color.size();
printf("Case %d: %d nodes not reachable from node %d with TTL = %d.\n",++cas,c,node,dis);
}
}
return 0;
}
void BFS(int root)
{
color[root]=1;
cost[root]=0;
Q.push(root);
while(!Q.empty())
{
int u=Q.front();
Q.pop();
for(int i=0; i<v[u].size(); i++)
{
int num=v[u][i];
if(color[num]==0)
{
cost[num]=cost[u]+1;
color[num]=1;
Q.push(num);
}
}
}
}
#define READ freopen("input.txt","r",stdin);
#define WRITE freopen("output.txt","w",stdout);
using namespace std;
void BFS(int a);
map<int,int>color;
map<int,int>cost;
map<int,int>no_of_node;
map<int,int>::iterator it;
vector<int>v[100000];
int row,col;
queue<int>Q;
int x[]= {-1,+0,+1,+0};
int y[]= {+0,-1,+0,+1};
int main()
{
//READ WRITE
int edge,cas=0;
while(scanf("%d",&edge)==1&&edge!=0)
{
color.clear();
cost.clear();
no_of_node.clear();
for(int i=0;i<100000;i++) v[i].clear();
for(int a=0; a<edge; a++)
{
int x,y;
scanf("%d %d",&x,&y);
v[x].push_back(y);
v[y].push_back(x);
no_of_node[x]++;
no_of_node[y]++;
}
int node,dis;
while(scanf("%d %d",&node,&dis)==2)
{
if(node==0&&dis==0) break;
color.clear();
cost.clear();
int c=0;
BFS(node);
for( it=cost.begin(); it!=cost.end(); it++)
{
if(it->second>dis) c++;
}
c+=no_of_node.size()-color.size();
printf("Case %d: %d nodes not reachable from node %d with TTL = %d.\n",++cas,c,node,dis);
}
}
return 0;
}
void BFS(int root)
{
color[root]=1;
cost[root]=0;
Q.push(root);
while(!Q.empty())
{
int u=Q.front();
Q.pop();
for(int i=0; i<v[u].size(); i++)
{
int num=v[u][i];
if(color[num]==0)
{
cost[num]=cost[u]+1;
color[num]=1;
Q.push(num);
}
}
}
}
কোন মন্তব্য নেই:
একটি মন্তব্য পোস্ট করুন