Cod sursa(job #3295112)

Utilizator DrugeaCasiandrugea DrugeaCasian Data 2 mai 2025 13:11:56
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.34 kb
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <vector>
#include <algorithm>

using namespace std;

vector<vector<int>> adj;
vector<int> dist;

pair<int, int> bfs(int start_node, int n) {
    fill(dist.begin(), dist.end(), -1);

    queue<int> q;

    dist[start_node] = 1;
    q.push(start_node);

    int farthest_node = start_node;
    int max_dist = 1;

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

        for (int v : adj[u]) {
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                q.push(v);

                if (dist[v] > max_dist) {
                    max_dist = dist[v];
                    farthest_node = v;
                }
            }
        }
    }

    return {farthest_node, max_dist};
}

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

    int n;
    fin >> n;

    adj.resize(n + 1);
    dist.resize(n + 1);

    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        fin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    pair<int, int> result1 = bfs(1, n);
    int endpoint1 = result1.first;

    pair<int, int> result2 = bfs(endpoint1, n);
    int diameter = result2.second;

    fout << diameter << endl;

    return 0;
}