Cod sursa(job #2469004)

Utilizator Leonard1998Olariu Leonard Leonard1998 Data 6 octombrie 2019 13:28:01
Problema Diametrul unui arbore Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.07 kb
#include <bits/stdc++.h>
#include <vector>
#include <queue>
#define NMAX (int)(1e5 + 5)

using namespace std;

int n, x, y;
vector<int> arb[NMAX];
queue<int> q;

struct node {
    bool visited;
    int dist;
} nodes[NMAX];

int BFS(int x) {
    nodes[x].visited = true;
    q.push(x);

    int curr;
    while (!q.empty()) {
        curr = q.front();
        q.pop();

        for (int next : arb[curr])
            if (!nodes[next].visited) {
                nodes[next].visited = true;
                nodes[next].dist = nodes[curr].dist+1;
                q.push(next);
            }
    }

    return curr;
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i < n; ++i) {
        scanf("%d %d", &x, &y);
        arb[x].push_back(y);
        arb[y].push_back(x);
    }

    for (int i = 1; i <= n; ++i) nodes[i].dist = 0, nodes[i].visited = false;
    int end1 = BFS(1);

    for (int i = 1; i <= n; ++i) nodes[i].dist = 0, nodes[i].visited = false;
    int end2 = BFS(end1);

    printf("%d\n", nodes[end2].dist + 1);
    return 0;
}