Cod sursa(job #2238433)

Utilizator dragos192k1Dragos-Iulian Galeteanu dragos192k1 Data 5 septembrie 2018 18:05:00
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <cstdio>
#include <cstdlib>
#include <queue>

using namespace std;

int n, mx_dist, last, d[100005], *a[100005];
queue <int> c;

void bfs(int x)
{
    d[x] = 1;
    c.push(x);

    while (!c.empty()) {
        int x = c.front();

        for (int i = 1; i <= a[x][0]; ++i)
            if (!d[a[x][i]]) {
                d[a[x][i]] = d[x] + 1;
                mx_dist = d[a[x][i]];
                last = a[x][i];
                c.push(a[x][i]);
            }

        c.pop();
    }

    for (int i = 1; i <= n; ++i) d[i] = 0;
}

int main()
{
    FILE *in, *out;
    in = freopen("darb.in", "r", stdin);
    out = freopen("darb.out", "w", stdout);

    scanf("%d", &n);

    for (int i = 1; i <= n; ++i) {
        a[i] = (int *)realloc(a[i], sizeof(int));
        a[i][0] = 0;
    }

    for (int i = 1; i < n; ++i) {
        int x, y;
        scanf("%d%d", &x, &y);

        ++a[x][0];
        a[x] = (int *)realloc(a[x], (a[x][0] + 1) * sizeof(int));
        a[x][a[x][0]] = y;

        ++a[y][0];
        a[y] = (int *)realloc(a[y], (a[y][0] + 1) * sizeof(int));
        a[y][a[y][0]] = x;
    }

    fclose(in);

    bfs(1);
    bfs(last);

    printf("%d", mx_dist);

    fclose(out);
    return 0;
}