Pagini recente » Cod sursa (job #1570958) | Cod sursa (job #3128864) | Cod sursa (job #1006958) | Cod sursa (job #246841) | Cod sursa (job #1870718)
#include <fstream>
#include <queue>
#define NMAX 100001
using namespace std;
int vt[NMAX], N; // VECTORUL DE TATI SI NUMARUL DE NODURI
bool viz[NMAX]; // VECTORUL DE VIZITATI
queue < pair < int , int > > coada;
int diametru, aux;
// int a[NMAX][NMAX];
void Citire()
{
ifstream fin("darb.in");
int x, y;
fin >> N;
for (int i = 1;i < N;i++)
{
fin >> x >> y;
vt[y] = x;
}
fin.close();
}
void Parcurgere(int start)
{
viz[start] = true; // VIZITAM POZITIA DE START
coada.push(make_pair(start, 1)); // BAGAM IN COADA POZITIA DE START
while (!coada.empty())
{
int nod = coada.front().first;
int pasi = coada.front().second;
if (pasi > diametru)
{
diametru = pasi;
aux = nod;
}
coada.pop();
if (vt[nod] != 0)
{
if (!viz[vt[nod]])
{
coada.push(make_pair(vt[nod],pasi + 1));
viz[vt[nod]] = true;
}
}
for (int i = 1;i <= N;i++)
{
if ((vt[i] == nod) && (!viz[i]))
{
coada.push(make_pair(i, pasi + 1));
viz[i] = true;
}
}
}
}
int main()
{
ofstream fout("darb.out");
Citire();
Parcurgere(1);
for (int i = 1;i <= N;i++)
viz[i] = false;
Parcurgere(aux);
fout << diametru;
return 0;
}