Cod sursa(job #3230282)

Utilizator Sabin1133Padurariu Sabin Sabin1133 Data 20 mai 2024 13:49:33
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.25 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>

void bfs(int source, std::vector<std::vector<int>> &adj, std::vector<int> &d)
{
    std::queue<int> q;

    for (auto &dist : d)
        dist = -1;

    d[source] = 0;
    q.push(source);

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

        for (auto neigh : adj[node]) {
            if (d[neigh] == -1) {
                d[neigh] = d[node] + 1;
                q.push(neigh);
            }
        }
    }
}

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

    int n, second_source, diam;
    std::vector<std::vector<int>> adj;
    std::vector<int> d;


    fin >> n;

    adj.resize(n);
    d.resize(n);

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

    bfs(0, adj, d);

    second_source = 0;

    for (int v = 1; v < n; ++v)
        if (d[v] > d[second_source])
            second_source = v;

    bfs(second_source, adj, d);

    diam = 0;

    for (int v = 0; v < n; ++v)
        diam = std::max(diam, d[v]);

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


    fin.close();
    fout.close();

    return 0;
}