Pagini recente » Cod sursa (job #162230) | Cod sursa (job #1413440) | Cod sursa (job #124175) | Cod sursa (job #1138185) | Cod sursa (job #1294031)
#include <stdio.h>
#include <iostream>
using namespace std;
const int N=100001,M=200001;
int vf[M],urm[M],lst[N];//listele
int coada[M],d[N];//in bfs
bool ver[N];
int fiu[N],scor[N];//in dfs
int nr,n,m,k;
int st=1;
int dr=0;
void adauga(int x, int y){
nr++;
vf[nr]=y;
urm[nr]=lst[x];
lst[x]=nr;
}
void bfs(int x)
{
int p,y;
coada[++dr]=x;
for(int i=1;i<=n;i++) d[i]=-1;
d[x]=0;
while (st<=dr)
{
x=coada[st++];
p=lst[x];
while(p!=0){
y=vf[p];
if(d[y]==-1){
d[y]=1+d[x];
coada[++dr]=y;
}
p=urm[p];
}
}
}
void bfs2(int x)
{
int p,y;
st=1;
dr=0;
coada[++dr]=x;
for(int i=1;i<=n;i++) d[i]=-1;
d[x]=0;
while (st<=dr)
{
x=coada[st++];
p=lst[x];
while(p!=0){
y=vf[p];
if(d[y]==-1){
d[y]=1+d[x];
fiu[y]=x;
coada[++dr]=y;
}
p=urm[p];
}
}
}
void citre(){
FILE *in;
in=fopen("darb.in","r");
fscanf(in,"%d",&n);
int a,b;
for(int i=1;i<=n;i++){
fscanf(in,"%d%d",&a,&b);
adauga(a,b);
adauga(b,a);
}
fclose(in);
}
int main()
{
FILE *out;
out=fopen("darb.out","w");
citre();
bfs(1);//luam un nod oarecare si gasim cea mai indepartata frunza
int maxim=-1,pmax;
for(int i=1;i<=n;i++)
if(maxim<d[i]){
maxim=d[i];
pmax=i;
}
// for(int i=1;i<=n;i++) cout<<d[i]<<" ";
//cout<<pmax;
bfs2(pmax);// gasim drumul care coincide cu drumul din nod spre cea mai indepartata frunza
maxim=-1;
for(int i=1;i<=n;i++)
if(maxim<d[i]){
maxim=d[i];
pmax=i;
}
int p=pmax,cnt=0;
while(fiu[p]!=0) {cnt++; p=fiu[p];}
fprintf(out,"%d\n",cnt+1);
/*
fprintf(out,"%d ",pmax);
while(fiu[pmax]!=0){
fprintf(out,"%d ",fiu[pmax]);
pmax=fiu[pmax];
}
fclose(out);
*/
return 0;
}