Pagini recente » Cod sursa (job #544858) | Cod sursa (job #1825021) | Cod sursa (job #1404027) | Cod sursa (job #226519) | Cod sursa (job #1320692)
#include <fstream>
#include <vector>
#define nmax 100005
using namespace std;
vector<int>G[nmax];
int v[nmax],ok,lg,n,d[nmax],lgmax,s;
void DFS(int x,int lg){
v[x]=1;
for(vector<int>::iterator it=G[x].begin();it!=G[x].end();it++)
if(!v[*it])DFS(*it,lg+1);
if(lg>lgmax) {lgmax=lg;s=x;}
}
void Attack(int si,int sf){
int Q[nmax],k,i,j;
k=1;
for(i=1;i<=n;i++)d[i]=-1;
d[si]=0;
Q[1]=si;
for(i=1;i<=k;i++)
for(j=0;j<G[Q[i]].size();j++)
if(d[G[Q[i]][j]]==-1||d[G[Q[i]][j]] > 1+d[Q[i]]){
d[G[Q[i]][j]]=d[Q[i]]+1;
Q[++k]=G[Q[i]][j];
}
}
int main(){
int i,x,y,si,sf;
ifstream fin("darb.in");
fin>>n;
for(i=1;i<n;i++){
fin>>x>>y;
G[x].push_back(y);
G[y].push_back(x);
}
fin.close();
DFS(1,1);
si=s;
ok=0;
for(i=1;i<=n;i++)
v[i]=0;
lgmax=0;
DFS(s,1);
sf=s;
Attack(si,sf);
ofstream fout("darb.out");
fout<<d[sf]+1<<'\n';
fout.close();
return 0;
}