Cod sursa(job #2138473)

Utilizator andra_moldovanAndra Moldovan andra_moldovan Data 21 februarie 2018 17:52:48
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include <fstream>
#include <vector>
#include <cstring>
#include <queue>

#define MAXN 100005

using namespace std;

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

int N, poz, viz[MAXN];

vector <int> graph[MAXN];
queue <int> Q;

inline void Read() {
    int x, y;

    fin >> N;

    for (int i = 1; i < N; i++) {
        fin >> x >> y;

        graph[x].push_back(y);
        graph[y].push_back(x);
    }
}

inline void BFS(int start) {
    int z;

    Q.push(start); viz[start] = 1;

    while (!Q.empty()) {
        z = Q.front();

        for (auto x : graph[z]) {
            if (!viz[x]) {
                viz[x] = viz[z] + 1;
                Q.push(x);
            }
        }

        Q.pop();
    }
}

inline void Solve() {
    BFS(1);

    for (int i = 1; i <= N; i++) {
        if (viz[i] > viz[poz])
            poz = i;
    }

    memset(viz, 0, sizeof(viz));
    BFS(poz); poz = 0;

    for (int i = 1; i <= N; i++) {
        if (viz[i] > viz[poz])
            poz = i;
    }

    fout << viz[poz];
}

int main () {
    Read();
    Solve();

    fin.close(); fout.close(); return 0;
}