Cod sursa(job #1688735)

Utilizator razvan242Zoltan Razvan-Daniel razvan242 Data 13 aprilie 2016 18:19:39
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <bits/stdc++.h>

using namespace std;

#define pb push_back

ifstream fin("darb.in");
ofstream fout("darb.out");

const int NMAX = 1e5 + 1;

int n;
vector<int> v[NMAX];
int len[NMAX], diameter, last;
bool viz[NMAX];

inline void bfs(int nod) {
    for (int i = 1; i <= n; ++i) {
        len[i] = 0;
        viz[i] = 0;
    }
    queue<int> Q;
    Q.push(nod);
    len[nod] = 1;
    viz[nod] = 1;
    int x;
    while (Q.size()) {
        x = Q.front();
        Q.pop();
        for (const int& y: v[x]) {
            if (!viz[y]) {
                Q.push(y);
                len[y] = len[x] + 1;
                viz[y] = 1;
                diameter = len[y];
                last = y;
            }
        }
    }
}

int main()
{
    fin >> n;
    for (int i = 1, x, y; i < n; ++i) {
        fin >> x >> y;
        v[x].pb(y);
        v[y].pb(x);
    }
    len[1] = 1;
    bfs(1);
    bfs(last);
    fout << diameter << '\n';
    return 0;
}