#include<bits/stdc++.h> using namespace std; #define pb push_back class Graph{ int V; list<int>*adj; public: Graph(int V){this->V=V; adj=new list<int>[V];} ~Graph(){delete []adj;} void addEdge(int u,int v){ adj[u].pb(v);} void BFS(int s) { if (adj[s].size()==0) {printf("0\n"); return;} bool visited[V]; memset(visited,false,sizeof(visited)); int level[V]; int cnt[V]={0}; list<int>q; list<int>::iterator i; q.pb(s); visited[s]=true; level[s]=0; int d,m=0; while (!q.empty()) { s=q.front(); q.pop_front(); cnt[level[s]]++; for (i=adj[s].begin();i!=adj[s].end();++i) { if (!visited[*i]) { q.pb(*i); visited[*i]=true; level[*i]=level[s]+1; } } } for (int j=1;j<=level[s];j++) if (m<cnt[j]) { m=cnt[j]; d=j; } printf("%d %d\n",m,d); return; } }; int main() { int e; while (scanf("%d",&e)!=EOF) { Graph g(e); int n,v; for (int i=0;i<e;i++) { scanf("%d",&n); while (n--) { scanf("%d",&v); g.addEdge(i,v); } } int t,s; scanf("%d",&t); while (t--) { scanf("%d",&s); g.BFS(s); } } return 0; }
Wednesday, August 24, 2016
UVA 924 - Spreading The News- Solution
Unknown
Studying at Shahjalal University of Science and Technology, Sylhet.
Subscribe to:
Post Comments (Atom)
0 comments:
Post a Comment