Pagini recente » Cod sursa (job #2747031) | Cod sursa (job #1320736) | Cod sursa (job #2681733) | Cod sursa (job #266683) | Cod sursa (job #1318009)
#include <stdio.h>
#define MAXN 100000
int nod[2 * MAXN + 1], next[2 * MAXN + 1], ult[MAXN + 1];
inline int max2(int a, int b){
return a > b ? a : b;
}
inline void add(int x, int y, int *k){
nod[*k] = y;
next[*k] = ult[x];
ult[x] = *k;
(*k)++;
}
int dfs(int prev, int x, int *d){
int poz = ult[x], rez, nodf = x, df = *d, aux;
while(poz != 0){
if(nod[poz] != prev){
aux = (*d) + 1;
rez = dfs(x, nod[poz], &aux);
if(aux > df){
df = aux;
nodf = rez;
}
}
poz = next[poz];
}
*d = df;
return nodf;
}
int bfs(int x){
int qu[MAXN], dist[MAXN], i, st = 0, dr = 1, poz;
char tr[MAXN];
for(i = 0; i <= MAXN; i++)
tr[i] = 0;
qu[0] = x;
dist[0] = 1;
tr[x] = 1;
while(st < dr){
poz = ult[qu[st]];
while(poz > 0){
if(!tr[nod[poz]]){
tr[nod[poz]] = 1;
qu[dr] = nod[poz];
dist[dr] = dist[st] + 1;
dr++;
}
poz = next[poz];
}
st++;
}
return dist[dr - 1];
}
int main(){
FILE *in = fopen("darb.in", "r");
int n, i, x, y, dr = 1;
fscanf(in, "%d", &n);
for(i = 0; i < n; i++){
fscanf(in, "%d%d", &x, &y);
add(x, y, &dr);
add(y, x, &dr);
}
fclose(in);
int aux = 0;
FILE *out = fopen("darb.out", "w");
fprintf(out, "%d", bfs(dfs(0, 1, &aux)));
fclose(out);
return 0;
}