#include<cstdio> #include<vector> #include<queue> #include<map> using namespace std; map<int,bool>visit; int bfs(map<int , vector <int > >graph, int source, int ttl) { int count=1,f,node,size; queue<int > q; map<int,int>level; level[source]=ttl; visit[source]=true; q.push(source); while (!q.empty()) { f=q.front(); q.pop(); if (level[f]==0) break; size=graph[f].size(); for (int i=0;i<size;i++) { node=graph[f][i]; if (visit[node]==false) { q.push(node); visit[node]=true; level[node]=level[f]-1; count++; } } } visit.clear(); return count; } int main() { int node,edge,case_no=1,a,b,source,ttl; while (scanf("%d",&edge) && edge) { map <int,vector <int > >graph; for (int i=0;i<edge;i++) { scanf("%d%d",&a,&b); graph[a].push_back(b); graph[b].push_back(a); visit[a]=false; visit[b]=false; } while (scanf("%d%d",&source,&ttl)==2) { if (source==0 && ttl==0) break; int visited=bfs(graph,source,ttl); printf("Case %d: %d nodes not reachable from node %d with TTL = %d.\n",case_no++,graph.size()-visited,source,ttl); } } return 0; }
Sunday, June 12, 2016
uva :336 - A Node Too Far
Unknown
Studying at Shahjalal University of Science and Technology, Sylhet.
Subscribe to:
Post Comments (Atom)
0 comments:
Post a Comment