Cod sursa(job #3300450)

Utilizator _andr31Rusanescu Andrei-Marian _andr31 Data 15 iunie 2025 21:48:12
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.27 kb
#include <bits/stdc++.h>

using namespace std;

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

    int n;
    fin >> n;
    vector<vector<int>> adj(n + 1);
    vector<int> dist(n + 1, INT_MAX);
    for (int i = 0, x, y; i < n - 1; ++i) {
        fin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    fin.close();


    queue<int> q;
    q.push(1);
    dist[1] = 0;
    int maxx = 0, id = -1;
    while (!q.empty()) {
        int nod = q.front(); q.pop();
        for (int vec : adj[nod]) {
            if (dist[vec] > dist[nod] + 1) {
                dist[vec] = dist[nod] + 1;
                q.push(vec);
                if (dist[vec] > maxx) {
                    maxx = dist[vec];
                    id = vec;
                }
            }
        }
    }

    for (int i = 0; i < n + 1; ++i)
        dist[i] = INT_MAX;

    maxx = 0;
    dist[id] = 0;
    q.push(id);
    while (!q.empty()) {
        int nod = q.front(); q.pop();
        for (int vec : adj[nod]) {
            if (dist[vec] > dist[nod] + 1) {
                dist[vec] = dist[nod] + 1;
                q.push(vec);
                if (dist[vec] > maxx)
                    maxx = dist[vec];
            }
        }
    }

    fout << maxx + 1 << '\n';


    return 0;
}