Advertisement
CodigoL

Empresa C++II

Oct 1st, 2016
75
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.06 KB | None | 0 0
  1. #include <iostream>
  2. #include <map>
  3. #include <vector>
  4. #include <queue>
  5. #include <fstream>
  6. #define INF (1 << 30) ///(2^30) * 1
  7. using namespace std;
  8. ifstream FE("empresa.in");
  9. map <string, int> Nombres;
  10. map <int,string> Numeros;
  11. int NN=0,iniN;
  12. int Agregar(string sss)
  13. {if(Nombres[sss])return Nombres[sss];
  14.  else{Nombres[sss]=NN; NN++; Numeros[NN-1]=sss;return NN-1;}
  15. }
  16. map <string, int> maximun;
  17. int maximan=0;
  18. int maxd=0;
  19. struct Grafo
  20. {
  21.     vector <vector <int> > adj;
  22.     void bfs(int n)
  23.     { int n2=n;
  24.         queue <int> cola;
  25.         vector <int> d(NN, INF);
  26.         int dmax=0;
  27.         d[n] = 0;
  28.         cola.push(n);
  29.  
  30.         while(cola.size())
  31.         {
  32.             n = cola.front();
  33.             cola.pop();
  34.  
  35.             for(unsigned int i=0; i< adj[n].size(); i++)
  36.             {
  37.                 if(d[n] + 1 < d[adj[n][i]])
  38.                 {
  39.                     d[adj[n][i]] = d[n] + 1;
  40.                     cola.push(adj[n][i]);
  41.                 }
  42.             }
  43.         }
  44.       //  cout<<endl<<endl;
  45.       ///  for(int i=0; i<NN; i++)
  46.       ///      cout << Numeros[i]<<" "<<d[i] << "  ";
  47.       //  cout << endl;
  48.        if(n2==0)
  49.        for(int i=0;i<NN;i++)
  50.         {maxd=max(maxd,d[i]);
  51.  
  52.         }
  53.        for(int i=0;i<NN;i++)
  54.        {if(maximun[Numeros[i]]<d[i])
  55.         {maximun[Numeros[i]]=d[i];
  56.             if(d[i]>=maxd)
  57.             {maxd=d[i];
  58.                 bfs(i);
  59.             }
  60.  
  61.         }
  62.  
  63.        }
  64.         ///Acá están las MINIMAS distancias desde el inicio a todos los nodos
  65.  
  66.  
  67.     }
  68.  
  69.     void Leer()
  70.      { string a,b;
  71.      int an,bn;
  72.  // cout<<"X"<<endl;
  73.          FE>>iniN;
  74.          adj.resize(iniN*2);
  75.          for(int i=0;i<iniN;i++)
  76.          {FE>>a>>b;
  77.           an=Agregar(a);
  78.           bn=Agregar(b);
  79.           adj[an].push_back(bn);
  80.           adj[bn].push_back(an);
  81.          // cout<<i<<endl;
  82.          }
  83.  
  84.  
  85.      }
  86.  
  87. };
  88. int main()
  89. {Grafo B;
  90.  B.Leer();
  91.  B.bfs(0);
  92.  FE.close();
  93.  ofstream FS ("empresa.out");
  94.  FS<<maxd<<endl;
  95.  for(auto i:maximun)
  96.  {if(i.second==maxd)FS<<i.first<<" ";
  97.  }
  98. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement