Cod sursa(job #2787935)

Utilizator Bogdan.paun50Mandresi Bogdan Bogdan.paun50 Data 24 octombrie 2021 13:29:03
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.13 kb
#include <fstream>
#include <vector>

using namespace std;

vector<int> l[100005];

int n, c[100005], d[100005], x, y, u, p, prim;

bool ok[100005];

int main()
{
    ifstream fin("darb.in");
    ofstream fout("darb.out");
    fin >> n;
    for(int i = 1; i < n; i++)
    {
        fin >> x >> y;
        l[x].push_back(y);
        l[y].push_back(x);
    }
    u = p = 1;
    c[1] = ok[1] = 1;
    while(p <= u)
    {
        for(int i = 0; i < l[c[p]].size(); i++)
            if(ok[l[c[p]][i]] == 0)
            {
                u++;
                c[u] = l[c[p]][i];
                ok[l[c[p]][i]] = 1;
            }
        p++;
    }
    prim = c[u];
    p = u = 1;
    for(int i = 1; i <= n; i++)
        ok[i] = 0;
    c[1] = prim;
    d[1] = 1;
    ok[prim] = 1;
    while(p <= u)
    {
        for(int i = 0; i < l[c[p]].size(); i++)
            if(ok[l[c[p]][i]] == 0)
            {
                u++;
                c[u] = l[c[p]][i];
                d[u] = d[p] + 1;
                ok[l[c[p]][i]] = 1;
            }
        p++;
    }
    fout << d[u] << "\n";
    return 0;
}