Pagini recente » Cod sursa (job #1259773) | Cod sursa (job #38516) | Istoria paginii runda/oni2009_ziua1/clasament | Cod sursa (job #654681) | Cod sursa (job #1908252)
#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
using namespace std;
/// http://www.infoarena.ro/problema/darb
ifstream fin ("darb.in");
ofstream fout ("darb.out");
int N, M, nod, d[100002];
bool viz[100002];
vector <int> L[100002];
void BFS(int k)
{
int j, i, maxim;
queue <int> q;
viz[k]=1;
q.push(k);
while (!q.empty())
{
k=q.front();
q.pop();
for (j=0; j<L[k].size(); j++)
{
i = L[k][j];
if (!viz[i])
{
q.push(i);
d[i] = d[k] + 1;
viz[i]=1;
}
}
}
maxim=0; nod=0;
for (i=1; i<=N; i++)
if (d[i] > maxim)
{
maxim = d[i];
nod = i;
}
}
void BFS2(int k)
{
int j, i, maxim;
queue <int> q;
for (i=1; i<=N; i++)
viz[i]=0, d[i]=0;
viz[k]=1;
q.push(k);
while (!q.empty())
{
k=q.front();
q.pop();
for (j=0; j<L[k].size(); j++)
{
i = L[k][j];
if (!viz[i])
{
q.push(i);
d[i] = d[k] + 1;
viz[i]=1;
}
}
}
maxim=0;
for (i=1; i<=N; i++)
if (d[i] > maxim)
maxim = d[i];
fout << ++maxim << "\n";
}
int main ()
{
int i, j, x, y;
fin >> N;
for (i=1; i<N; i++)
{
fin >> x >> y;
L[x].push_back(y);
L[y].push_back(x);
}
BFS(1);
///cout << nod << endl;
/// extragem nod, rezultat al primei parcurgeri
BFS2(nod);
fin.close();
fout.close();
return 0;
}