|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 |
#include <iostream> #include <string.h> #include <vector> #include <queue> #define ll long long #define INF 10000000 using namespace std; vector<int> vb; vector<int> gr[2501]; int s,n; int daymap[2501]; void bfs(int src) { int day[2501]; bool visit[2501]; for(int i=0;i<2501;i++) { daymap[i]=-1; day[i]=-1; visit[i]=false; } visit[src]=1; day[0]+=1; daymap[src]=0; queue<int> q; q.push(src); int a; while(!q.empty()) { a = q.front(); q.pop(); for(int i=0;i<gr[a].size();i++) { if(visit[gr[a][i]]==0) { visit[gr[a][i]]=1; q.push(gr[a][i]); daymap[gr[a][i]]=daymap[a]+1; if(day[daymap[gr[a][i]]]==-1) day[daymap[gr[a][i]]] = 1; else day[daymap[gr[a][i]]]+=1; } } } int day_no=-1; int MX=0; for(int i=1;day[i]!=-1;i++) { if(day[i]>MX) { MX = day[i]; day_no = i; } } cout<<MX<<" "<<day_no<<"\n"; } int main() { int a,t,src; /*while(cin>>s) {*/ cin>>s; for(int i=0;i<s;i++) { cin>>n; gr[i].clear(); if(n==0) continue; while(n--) { cin>>a; gr[i].push_back(a); } }//s loop cin>>t; for(int i=0;i<t;i++) { cin>>src; if(gr[src].size()==0) { cout<<0<<"\n"; continue; } bfs(src); } //}//while return 0; } |