Pagini recente » Cod sursa (job #468609) | Cod sursa (job #689105) | Cod sursa (job #870013) | Cod sursa (job #631322) | Cod sursa (job #1316798)
#include <iostream>
#include <fstream>
#include <Vector>
#define nmax 100005
using namespace std;
vector<int>G[nmax];
int v[nmax],ok,s,n,d[nmax];
void DFS(int x){
v[x]=1;
for(vector<int>::iterator it=G[x].begin();it!=G[x].end();it++)
if(!v[*it])DFS(*it);
if(!ok){ok=1;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);
si=s;
ok=0;
for(i=1;i<=n;i++)
v[i]=0;
DFS(s);
sf=s;
Attack(si,sf);
ofstream fout("darb.out");
fout<<d[sf]+1<<'\n';
fout.close();
return 0;
}