Pagini recente » Cod sursa (job #1208026) | Cod sursa (job #492106) | Cod sursa (job #2536231) | Cod sursa (job #2038677) | Cod sursa (job #1268083)
#include <stdio.h>
#include <stdlib.h>
#define MAXN 100000
int k, q[MAXN+1], lista[MAXN+1], dist[MAXN+1], ok[MAXN+1], val[MAXN*2+1], next[MAXN*2+1];
inline void adauga(int a, int b){
k++;
val[k]=b;
next[k]=lista[a];
lista[a]=k;
}
inline void bfs(int sursa, int *last, int f){
int st, dr, p, x, y;
q[0]=sursa;
dist[sursa]=1;
ok[sursa]=f;
st=0;
dr=1;
while(st<dr){
x=q[st++];
p=lista[x];
while(p!=0){
y=val[p];
if(ok[y]!=f){
dist[y]=dist[x]+1;
ok[y]=f;
q[dr++]=y;
}
p=next[p];
}
}
(*last)=q[dr-1];
}
int main(){
int i, n, a, b, ult, prim;
FILE *fin, *fout;
fin=fopen("darb.in", "r");
fout=fopen("darb.out", "w");
fscanf(fin, "%d", &n);
for(i=1; i<n; i++){
fscanf(fin, "%d%d", &a, &b);
adauga(a, b);
adauga(b, a);
}
bfs(rand()%n+1, &ult, 1);
bfs(ult, &prim, 2);
fprintf(fout, "%d\n", dist[prim]);
fclose(fin);
fclose(fout);
return 0;
}