Cod sursa(job #1985411)

Utilizator rares96cheseliRares Cheseli rares96cheseli Data 27 mai 2017 20:51:53
Problema Diametrul unui arbore Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include <bits/stdc++.h>

#define NMAX 100005

using namespace std;

ifstream f("darb.in");
ofstream g("darb.out");

int N, x, y, last;
vector < int > G[NMAX];

void bfs(int source, vector < int > &dist) {
    dist[source] = 0;
    queue < int > Q;
    Q.push(source);

    while (Q.size()) {
        int node = Q.front();
        Q.pop();

        for (auto it : G[node]) {
            if (dist[node] + 1 < dist[it]) {
                dist[it] = dist[node] + 1;
                Q.push(it);
                last = it;
            }
        }
    }
}

int main() {
    f >> N;
    vector < int > dist(N + 1, (1 << 30));
    for (int i = 1; i < N; ++i) {
        f >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }

    bfs(1, dist);
    fill(dist.begin(), dist.end(), (1 << 30));
    bfs(last, dist);

    g << dist[last] << '\n';
}