Cod sursa(job #2998728)

Utilizator amcbnCiobanu Andrei Mihai amcbn Data 9 martie 2023 21:48:33
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.16 kb
// [A][M][C][B][N]
#include <bits/stdc++.h>
using namespace std;
const int inf = 2e9;
const int mod = 666013;
const char sp = ' ';
const char nl = '\n';
ifstream fin("darb.in");
ofstream fout("darb.out");

const int nmax = 1e5;
int n, l;
vector<int> g[nmax + 1];

void bfs(int root, vector<int>& dist) {
    vector<int> used(n + 1);
    queue<int> q;
    q.push(root), used[root] = 1;
    while (q.size()) {
        int curr = q.front();
        for (auto& next : g[curr]) {
            if (used[next]) {
                continue;
            }
            used[next] = 1;
            dist[next] = dist[curr] + 1;
            q.push(next);
        }
        q.pop();
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie();
    fin >> n;
    for (int q = 0; q < n - 1; ++q) {
        int v, u;
        fin >> v >> u;
        g[v].push_back(u);
        g[u].push_back(v);
    }
    vector<int> tmp(n + 1), ldist(n + 1);
    bfs(1, tmp), l = 1;
    for (int i = 1; i <= n; ++i) {
        if (tmp[l] < tmp[i]) {
            l = i;
        }
    }
    bfs(l, ldist);
    fout << *max_element(ldist.begin() + 1, ldist.end()) + 1;
}