Cod sursa(job #2198297)

Utilizator 24601Dan Ban 24601 Data 24 aprilie 2018 10:31:59
Problema Diametrul unui arbore Scor 70
Compilator c Status done
Runda Arhiva educationala Marime 1.42 kb
#include <stdio.h>
#include <string.h>
#include <unistd.h>

#define CHUNK (1 << 21)
#define NMAX 100000

static struct edge {
    size_t v;
    size_t n;
} e[NMAX];

static size_t d[NMAX+1], q[NMAX], g[NMAX+1], qh, qt, dmax, smax;

static char buf[CHUNK];
static size_t bpos;

static inline size_t read_int(void)
{
    size_t x = 0;

    while ('0' <= buf[bpos] && buf[bpos] <= '9') {
        x = x * 10 + (buf[bpos] - '0');
        bpos++;
    }

    bpos++;
    return x;
}

static inline void bfs(size_t s)
{
    size_t u;

    memset(d, 0xFF, sizeof d);

    qh = qt = 0;
    d[s] = 0;
    q[qt++] = s;
    while (qh < qt) {
        s = q[qh++];
        for (u = g[s]; u != 0; u = e[u].n) {
            if (d[s] + 1 < d[e[u].v]) {
                d[e[u].v] = d[s] + 1;
                q[qt++] = e[u].v;

                if (d[e[u].v] > dmax) {
                    dmax = d[e[u].v];
                    smax = e[u].v;
                }
            }
        }
    }
}

int main(void)
{
    size_t i, n, u, v;

    freopen("darb.in", "r", stdin);
    freopen("darb.out", "w", stdout);

    read(STDIN_FILENO, buf, CHUNK);

    n = read_int();

    for (i = 1; i <= n; i++) {
        u = read_int();
        v = read_int();

        e[2*i].v = u;
        e[2*i].n = g[v];
        g[v] = 2*i;

        e[2*i+1].v = v;
        e[2*i+1].n = g[u];
        g[u] = 2*i+1;
    }

    bfs(1);
    bfs(smax);

    printf("%lu", dmax + 1);

    return 0;
}