Cod sursa(job #1500723)

Utilizator bciobanuBogdan Ciobanu bciobanu Data 12 octombrie 2015 16:54:52
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include <cstdio>
#include <cstdlib>
#include <ctime>

using namespace std;

const int Nmax = 1e5;
const int NIL = -1;
const int Inf = 2e9;

struct List {
    int v, next;
};

List l[2 * Nmax];
int adj[Nmax];

int Q[Nmax], qstart, qend;
int dist[Nmax];
int n;

void addEdge(int u, int v, int pos) {
    l[pos].v = v;
    l[pos].next = adj[u];
    adj[u] = pos;
}

int bfs(int u) {
    for (int i = 0; i < n; i++) {
        dist[i] = Inf;
    }

    int v;
    Q[0] = u;
    qstart = 0;
    qend = 1;
    dist[u] = 1;
    do {
        u = Q[qstart++];
        for (int i = adj[u]; i != NIL; i = l[i].next) {
            if (dist[l[i].v] > dist[u] + 1) {
                v = l[i].v;
                dist[v] = dist[u] + 1;
                Q[qend++] = v;
            }
        }
    } while (qstart != qend);
    return v;
}

int main(void) {
    freopen("darb.in", "r", stdin);
    freopen("darb.out", "w", stdout);
    int u, v;

    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        adj[i] = NIL;
    }
    for (int i = 1; i < n; i++) {
        scanf("%d%d", &u, &v);
        addEdge(u - 1, v - 1, 2 * i - 2);
        addEdge(v - 1, u - 1, 2 * i - 1);
    }
    fclose(stdin);

    srand(time(0));
    printf("%d\n", dist[bfs(bfs(rand() % n))]);
    fclose(stdout);
    return 0;
}