problem link: A node too far
Solution code:
#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#include<stack>
#include<queue>
#include<stack>
#include<map>
using namespace std;
vector<int>my[100001];
int source,TTL,total;
int calling_bfs()
{
//cout<<total<<endl;
queue<int>layer;
layer.push(source);
//cout<<source<<endl;
map<int,int>l;
// for(int i=1;i<=5;i++)
// cout<<l[i]<<endl;
l[source]=1;
total--;
while(!layer.empty())
{
int v=layer.front();layer.pop();
for(int i=0;i<my[v].size() && l[v]<=TTL;i++)
{
int u=my[v][i];
if(l[u]==0)
{
l[u]=1+l[v];
layer.push(u);
total--;
}
}
}
}
int main()
{
//freopen("c:\\temp\\in.txt","r",stdin);
int nc;
int u,v,ca=1;
while(scanf("%d",&nc)==1 && nc)
{
total=0;
map<int,bool>l;
for(int i=1;i<=nc;i++)
{
scanf("%d %d",&u,&v);
my[u].push_back(v);
my[v].push_back(u);
if(l[u]==0)
{
l[u]=1;total++;
}
if(l[v]==0)
{
l[v]=1;
total++;
}
}
int c=total;
while(scanf("%d %d",&source,&TTL)==2)
{
if(source==0 && TTL==0)
break;
total=c;
if(TTL==0)
printf("Case %d: %d nodes not reachable from node %d with TTL = %d.\n",ca++,total-1,source,TTL);
else
{
calling_bfs();
printf("Case %d: %d nodes not reachable from node %d with TTL = %d.\n",ca++,total,source,TTL);
}
}
for(int i=0;i<=100000;i++)
my[i].clear();
}
return 0;
}
0 comments:
একটি মন্তব্য পোস্ট করুন