Cod sursa(job #2358211)

Utilizator AndreiBadescuBadescu Andrei-Octavian AndreiBadescu Data 27 februarie 2019 22:22:40
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.02 kb
#include <fstream>
#include <vector>
#include <queue>

using namespace std;
typedef unsigned int uint;

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

uint n;
vector<vector<uint>> adj;

uint BFS(uint node, vector<uint> &v)
{
    queue<uint> Q;
    Q.push(node);

    v[node] = 1;
    while (!Q.empty())
    {
        node = Q.front();
        Q.pop();

        for (auto &i : adj[node])
        {
            if (!v[i])
            {
                v[i] = 1 + v[node];
                Q.push(i);
            }
        }
    }

    uint ind, ma = 0;
    for (uint i = 1; i <= n; ++i)
        if (v[i] > ma)
        {
            ma = v[i];
            ind = i;
        }

    return ind;
}

int main()
{
    fin >> n;

    adj.assign(n + 1, vector<uint>());

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

    vector<uint> v1(n + 1, 0), v2(n + 1, 0);
    fout << v2[BFS(BFS(1,v1),v2)];
}