Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <map>
- #include <vector>
- #include <queue>
- #include <fstream>
- #define INF (1 << 30) ///(2^30) * 1
- using namespace std;
- ifstream FE("empresa.in");
- map <string, int> Nombres;
- map <int,string> Numeros;
- int NN=0,iniN;
- int Agregar(string sss)
- {if(Nombres[sss])return Nombres[sss];
- else{Nombres[sss]=NN; NN++; Numeros[NN-1]=sss;return NN-1;}
- }
- map <string, int> maximun;
- int maximan=0;
- int maxd=0;
- struct Grafo
- {
- vector <vector <int> > adj;
- void bfs(int n)
- { int n2=n;
- queue <int> cola;
- vector <int> d(NN, INF);
- int dmax=0;
- d[n] = 0;
- cola.push(n);
- while(cola.size())
- {
- n = cola.front();
- cola.pop();
- for(unsigned int i=0; i< adj[n].size(); i++)
- {
- if(d[n] + 1 < d[adj[n][i]])
- {
- d[adj[n][i]] = d[n] + 1;
- cola.push(adj[n][i]);
- }
- }
- }
- // cout<<endl<<endl;
- /// for(int i=0; i<NN; i++)
- /// cout << Numeros[i]<<" "<<d[i] << " ";
- // cout << endl;
- if(n2==0)
- for(int i=0;i<NN;i++)
- {maxd=max(maxd,d[i]);
- }
- for(int i=0;i<NN;i++)
- {if(maximun[Numeros[i]]<d[i])
- {maximun[Numeros[i]]=d[i];
- if(d[i]>=maxd)
- {maxd=d[i];
- bfs(i);
- }
- }
- }
- ///Acá están las MINIMAS distancias desde el inicio a todos los nodos
- }
- void Leer()
- { string a,b;
- int an,bn;
- // cout<<"X"<<endl;
- FE>>iniN;
- adj.resize(iniN*2);
- for(int i=0;i<iniN;i++)
- {FE>>a>>b;
- an=Agregar(a);
- bn=Agregar(b);
- adj[an].push_back(bn);
- adj[bn].push_back(an);
- // cout<<i<<endl;
- }
- }
- };
- int main()
- {Grafo B;
- B.Leer();
- B.bfs(0);
- FE.close();
- ofstream FS ("empresa.out");
- FS<<maxd<<endl;
- for(auto i:maximun)
- {if(i.second==maxd)FS<<i.first<<" ";
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement