Cod sursa(job #1268083)

Utilizator alexpetrescuAlexandru Petrescu alexpetrescu Data 20 noiembrie 2014 16:45:05
Problema Diametrul unui arbore Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 1.11 kb
#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;
}