Pagini recente » cerculdeinfo-lectia8-kmpzmanacher | Cod sursa (job #102654) | Cod sursa (job #541401) | Istoria paginii runda/vacanta_11_3 | Cod sursa (job #2510467)
#include <fstream>
#include <vector>
using namespace std;
vector <int> v[100001];
int dist1[100001],dist2[100001],c[100001];
int main()
{
ifstream fin ("dfs.in");
ofstream fout ("dfs.out");
int n,m,x,y,s,p=1,u=1;
fin>>n;
for (int i=1;i<n;i++)
{
fin>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
c[u]=1;
dist1[1]=1;
while (p<=u)
{
int vf=c[p];
p++;
int l=v[vf].size();
for (int i=0;i<l;i++)
{
if (dist1[v[vf][i]]==0)
{
u++;
c[u]=v[vf][i];
dist1[v[vf][i]]=dist1[vf]+1;
}
}
}
int imax=1;
int maxim=dist1[1];
for (int i=2;i<=n;i++)
if (dist1[i]>maxim)
{
maxim=dist1[i];
imax=i;
}
u=p=1;
c[u]=imax;
dist2[imax]=1;
while (p<=u)
{
int vf=c[p];
p++;
int l=v[vf].size();
for (int i=0;i<l;i++)
{
if (dist2[v[vf][i]]==0)
{
u++;
c[u]=v[vf][i];
dist2[v[vf][i]]=dist2[vf]+1;
}
}
}
maxim=dist2[1];
for (int i=2;i<=n;i++)
if (dist2[i]>maxim)
maxim=dist2[i];
fout<<maxim;
return 0;
}