Cod sursa(job #2762367)

Utilizator andreiiorgulescuandrei iorgulescu andreiiorgulescu Data 6 iulie 2021 18:10:22
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.5 kb
#include <bits/stdc++.h>

using namespace std;

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

int n,d1[100005],d2[100005],rad,t[100005],pst;
vector<int>a[100005];
queue<int>q;

void citire()
{
    in >> n;
    for (int i = 1; i < n; i++)
    {
        int x,y;
        in >> x >> y;
        a[x].push_back(y);
        a[y].push_back(x);
        t[y] = x;
    }
    for (int i = 1; i <= n; i++)
        if (t[i] == 0)
            rad = i;
}

void BFS1()
{
    q.push(rad);
    d1[rad] = 1;
    while (!q.empty())
    {
        int nod = q.front();
        q.pop();
        for (int i = 0; i < a[nod].size(); i++)
        {
            if (d1[a[nod][i]] == 0)
            {
                q.push(a[nod][i]);
                d1[a[nod][i]] = 1 + d1[nod];
            }
        }
    }
    int maxim = 0;
    for (int i = 1; i <= n; i++)
        if (d1[i] > maxim)
        {
            maxim = d1[i];
            pst = i;
        }
}

void BFS2()
{
    q.push(pst);
    d2[pst] = 1;
    while (!q.empty())
    {
        int nod = q.front();
        q.pop();
        for (int i = 0; i < a[nod].size(); i++)
        {
            if (d2[a[nod][i]] == 0)
            {
                q.push(a[nod][i]);
                d2[a[nod][i]] = 1 + d2[nod];
            }
        }
    }
    int maxim = 0;
    for (int i = 1; i <= n; i++)
        maxim = max(maxim,d2[i]);
    out << maxim;
}

int main()
{
    citire();
    BFS1();
    BFS2();
    return 0;
}