Cod sursa(job #3279435)

Utilizator denisdalanDenis Dalan denisdalan Data 22 februarie 2025 22:29:37
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.56 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <fstream>
using namespace std;

int maxi = 0;

int darb(int start, const vector<vector<int>>& g) {
    int n = g.size() - 1; // Nodes are 1-indexed
    vector<int> dist(n + 1, -1); // Initialize to -1 (unreachable)
    int nx = 0;

    //for (int start = 1; start <= n; ++start) {
        queue<int> q;
        q.push(start);
        dist[start] = 0;

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

            for (int v : g[u]) {
                if (dist[v] == -1) { // Not visited yet
                    dist[v] = dist[u] + 1;
                    q.push(v);
                    if (dist[v] > maxi) {
                        maxi = dist[v];
                        nx = v;
                    }
                }
            }
        }
    //}

    //for (int i = 1; i <= n; ++i)
    //{
        //cout << i << ": ";
        for (int j = 1; j < dist.size(); ++j)
            cout << dist[j] << ' ';
        cout << '\n';
    //}

    return nx;
}

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

    int n, x, y;

    in >> n;
    vector<vector<int>> g(n+1);

    while (in >> x >> y)
    {
        g[x].push_back(y);
        g[y].push_back(x);
    }

    auto st = darb(1, g);
    auto res = darb(st, g);

    /*for (int i = 1; i <= n; ++i)
    {
        cout << i << ": ";
        for (int j = 1; j < dist[i].size(); ++j)
            cout << dist[i][j] << ' ';
        cout << '\n';
    }*/

    out << maxi+1 << '\n';

    in.close();
    out.close();
    return 0;
}