Advertisement
Guest User

Untitled

a guest
Apr 16th, 2014
34
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.45 KB | None | 0 0
  1. #include <iostream>
  2. #include <sstream>
  3. #include <string>
  4. #include <algorithm>
  5. #include <queue>
  6. #include <cstdio>
  7.  
  8. //Variaveis Globais
  9. int n,indice,conta;
  10. int input[801][801];
  11.  
  12. //Funcoes Pre-Declaradas
  13. void imprime();
  14. int BFS();
  15.  
  16. using namespace std;
  17.  
  18. int main(){
  19.     int i,j,n_aux, maximo = 0, res;
  20.     string linha;
  21.  
  22.     while (scanf_s("%d", &n) != EOF){
  23.  
  24.         maximo = 0;
  25.         memset(input,0,sizeof(input));
  26.  
  27.         //Guardar os dados
  28.         for (i = 0; i < n; ++i){
  29.             scanf_s("%d", &input[i][0]);
  30.             if (input[i][0]>maximo){
  31.                 maximo = input[i][0];
  32.                 indice = i;
  33.             }
  34.             for (j = 1; j < input[i][0] + 1;j++){
  35.                 scanf_s("%d",&input[i][j]);
  36.             }
  37.            
  38.         }
  39.         if (input[0][0] == maximo && indice == 0)
  40.             cout << "King of popularity!\n";
  41.  
  42.         else{
  43.             res = BFS();
  44.             cout << res << endl;
  45.         }
  46.     }
  47.  
  48.  
  49.    
  50.     system("pause");
  51.     return 0;
  52. }
  53.  
  54.  
  55. void imprime(){
  56.     int i, j;
  57.     for (i = 0; i < n; ++i){
  58.         cout << endl;
  59.         for (j = 0; j < n; ++j){
  60.             cout << " " << input[i][j];
  61.         }
  62.     }
  63. }
  64.  
  65. int BFS(){
  66.     int v,i;
  67.     queue<int> fila;
  68.  
  69.     conta = 0;
  70.     bool visitado[800];
  71.     memset(visitado, false, sizeof(visitado));
  72.  
  73.     visitado[0] = true;
  74.     fila.push(0);
  75.  
  76.     while (!fila.empty()){
  77.         v = fila.front();
  78.         for (i = 1; i < input[v][0]+1; ++i){
  79.             if (!visitado[input[v][i] - 1]){
  80.                 visitado[input[v][i] - 1] = true;
  81.                 fila.push(input[v][i] - 1);
  82.  
  83.                 if (input[v][i] - 1 == indice)
  84.                     return conta;
  85.             }
  86.         }
  87.         conta++;
  88.         fila.pop();
  89.     }
  90.  
  91.     return 0;
  92. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement