Guest User

uva924

a guest
Jan 6th, 2018
79
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.85 KB | None | 0 0
  1. /******************************************************************************
  2.  
  3.                               Online C++ Compiler.
  4.                Code, Compile, Run and Debug C++ program online.
  5. Write your code in this editor and press "Run" button to compile and execute it.
  6.  
  7. *******************************************************************************/
  8.  
  9. #include <bits/stdc++.h>
  10. #define pb push_back
  11. using namespace std;
  12.  
  13. int m,d;
  14. struct node{
  15.     int n,d;
  16. };
  17.  
  18. vector<int> G[3000];
  19. bool visit[3000];
  20. int value[3000];
  21.  
  22. void bfs(int s){
  23.    
  24.     queue<node> Q;
  25.     node nod;
  26.     nod.n=s;
  27.     nod.d=1;
  28.     Q.push(nod);
  29.     visit[s] = true;
  30.    
  31.     while(!Q.empty()){
  32.         nod = Q.front();
  33.         Q.pop();
  34.         int u = nod.n;
  35.         int day = nod.d;
  36.         int cnt=0;
  37.        
  38.         for(int i=0;i<G[u].size();i++){
  39.             int v = G[u][i];
  40.             if(visit[v]==false){
  41.                 visit[v] = true;
  42.                 nod.n = v;
  43.                 nod.d = day+1;
  44.                 Q.push(nod);
  45.                 cnt++;
  46.             }
  47.         }
  48.        
  49.         value[day]+=cnt;
  50.         if(value[day]>m){
  51.             m = value[day];
  52.             d = day;
  53.         }
  54.        
  55.     }
  56. }
  57.  
  58. void print(){
  59.    
  60.     if(m==0)    printf("0\n");
  61.     else printf("%d %d\n",m,d);
  62.    
  63. }
  64.  
  65. int main()
  66. {
  67.     int e;
  68.     scanf("%d",&e);
  69.     getchar();
  70.     for(int i=0;i<e;i++){
  71.         int N;
  72.         scanf("%d",&N);
  73.         while(N--){
  74.             int f;
  75.             scanf("%d",&f);
  76.             G[i].pb(f);
  77.         }
  78.     }
  79.    
  80.     int t;
  81.     scanf("%d",&t);
  82.    
  83.     getchar();
  84.     while(t--){
  85.         int s;
  86.         scanf("%d",&s);
  87.         bfs(s);
  88.         print();
  89.         memset(visit,false,sizeof(visit));
  90.         memset(value,0,sizeof(value));
  91.         m=0;
  92.         d=0;
  93.     }
  94.  
  95.     return 0;
  96. }
Advertisement
Add Comment
Please, Sign In to add comment