336:A Node Too Far

Problem Link

<Source Code>

#include<bits/stdc++.h>
#define pb push_back
#define sf(x) scanf(“%d”,&x)
#define MN 1234567
#define max 10000
#define all(water) (water.begin(),water.end());
#define fr(i,a,b) for(i=a;i<b;i++)
using namespace std;
#define cln(a) memset(a,0,sizeof(a))
#define eof(a) memset(a,-1,sizeof(a))
#define pt(c) printf(“Case %d: “,++c)
#define ll long long
map<int,int>visited;
void bfs(int start, map<int,vector<int>>graph) {
queue<int>q;
q.push(start);
visited[start]=0;
while(!q.empty())
{
int u=q.front(),i;
q.pop();
int l=graph[u].size();
for(i=0;i<l;i++)
{
int v=graph[u][i];
if(!visited.count(v))
{
visited[v]=visited[u]+1;
q.push(v);
}
}
}
}
int main()
{
int c=0,node,i,start,ttl,res;
while(scanf(“%d”,&node) &&node)
{
map<int,vector<int>>graph;
int x,y;
while(node–)
{
cin>>x>>y;
graph[x].pb(y);
graph[y].pb(x);

}
while(scanf(“%d %d”,&start,&ttl) &&(start!=0 ||ttl!=0))
{
visited.clear();
map<int,int>::const_iterator it;
res=0;
bfs(start,graph);
for(it=visited.begin();it!=visited.end();it++)
{
if((*it).second>ttl)
res++;
}
res+=graph.size()-visited.size();

printf(“Case %d: %d nodes not reachable from node %d with TTL = %d.\n”,++c,res,start,ttl);
}
}

return 0;
}

Advertisements

About waprogramming

I am in CSE,from CUET
This entry was posted in Uncategorized, uva and tagged , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s