Cod sursa(job #3300452)

Utilizator ancamaximMaxim Anca Stefania ancamaxim Data 15 iunie 2025 22:40:02
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.01 kb
#include <bits/stdc++.h>

using namespace std;

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

int n;
vector<vector<int>> adj;

// 2 bfs
pair<int, int> bfs(int start) {
    int max_node = 0, max_val = 0;
    vector<int> d(n + 1, INT32_MAX);

    queue<int> q;
    q.push(start);
    d[start] = 0;

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

        for (int neigh : adj[node])
            if (d[node] + 1 < d[neigh]) {
                d[neigh] = 1 + d[node];
                q.push(neigh);

                if (max_val < d[neigh]) {
                    max_val = d[neigh];
                    max_node = neigh;
                }
            }
    }

    return {max_node, max_val};
}

int longest_dag_bfs() {
    auto [node, _] = bfs(1);

    return 1 + bfs(node).second;
}

int main() {
    fin >> n;
    adj.resize(n + 1);

    for (int x, y, i = 1; i < n; ++i) {
        fin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }

    fout << longest_dag_bfs() << "\n";

}