Cod sursa(job #2022935)

Utilizator StefanManolacheManolache Stefan StefanManolache Data 17 septembrie 2017 19:23:10
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include <cstdio>
#include <vector>

FILE *fin = fopen("darb.in", "r");
FILE *fout = fopen("darb.out", "w");

#define maxn 100000

std::vector<int> v[maxn + 1];

bool viz[maxn + 1];
int q[maxn + 1];
int st = 0;
int dr = 0;
int k;
int lmax;
int dist[maxn + 1];

inline void add (int t) {
    q[dr] = t;
    dr++;
    viz[t] = 1;
}
inline void del () {
    st++;
}

inline void bfs(int a) {
    st = 0;
    dr = 0;
    add(a);
    while (st <= dr) {
        for (auto y : v[q[st]]) {
            if (viz[y] != 1) {
                add(y);
                dist[y] = dist[q[st]] + 1;
                lmax = dist[y];
                k = y;
            }

        }
        del();
    }
}

int main()
{
    int n, x, y, rez = 0;
    fscanf(fin, "%d", &n);

    for (int i = 1; i <= n - 1; i++) {
        fscanf(fin, "%d%d", &x, &y);
        v[x].push_back (y);
        v[y].push_back (x);
    }
    bfs(1);
    for (int i = 1; i <= n ; i++) {
        dist[i] = 0;
        viz[i] = 0;
    }
    bfs(k);
    rez = lmax + 1;
    fprintf(fout, "%d", rez);
    return 0;
}