Cod sursa(job #2729757)

Utilizator EusebiudistrugatorulLionel Messi Eusebiudistrugatorul Data 25 martie 2021 11:38:02
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.33 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("darb.in");
ofstream fout("darb.out");
int const N = 1e5 + 10;
vector<int> nodes[N], visited(N), coada(N), length(N);

int BFS(int node) {
    int st = 0, dr = 0, length_max = 0, furthest_node = 1, aux = node;
    coada[dr++] = node;
    while (st < dr) {
        node = coada[st++];
        for (int i = 0; i < nodes[node].size(); ++i) {
            if (visited[nodes[node][i]] == 0) {
                visited[nodes[node][i]] = 1;
                coada[dr++] = nodes[node][i];
                length[nodes[node][i]] = length[node] + 1;
                if (length_max < length[nodes[node][i]]) {
                    furthest_node = nodes[node][i];
                }
                length_max = max(length_max, length[nodes[node][i]]);
            }
        }
    }
    if (aux == 1) {
        return furthest_node;
    }
    return length_max;
}

int main() {
    int n; fin >> n;
    for (int i = 1; i < n; ++i) {
        int nr_1, nr_2;
        fin >> nr_1 >> nr_2;
        nodes[nr_1].push_back(nr_2);
        nodes[nr_2].push_back(nr_1);
    }
    visited[1] = 1;
    int node = BFS(1);
    for (int i = 1; i <= N; ++i) {
        length[i] = visited[i] = 0;
    }
    visited[node] = 1;
    length[node] = 1;
    fout << BFS(node);
    return 0;
}