Cod sursa(job #2887178)

Utilizator pifaDumitru Andrei Denis pifa Data 8 aprilie 2022 22:43:09
Problema Diametrul unui arbore Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.04 kb
#include <bits/stdc++.h>

using namespace std;

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

int n;

int x[100001], a[10001][10001], viz[100001], tati[100001], distante[100001];

void bfs(int start)
{
    int k, st, dr;
    st = dr = 1;
    tati[start] = 0;
    x[1] = start;
    viz[start] = 1;
    while(st <= dr)
    {
        k = x[st];
        for(int i = 1; i <= n; i++)
        {
            if(viz[i] == 0 && a[k][i] == 1)
            {
                viz[i] = 1;
                x[++dr] = i;
                tati[i] = k;
                distante[i] = distante[k] + 1;
            }
        }
        st++;
    }
}

int main()
{
    in >> n;
    for(int te = 1; te <= n; te++)
    {
        int l, c;
        in >> l >> c;
        a[l][c] = 1;
        a[c][l] = 1;
    }
    bfs(1);
    int maxim = 0;
    vector <int> v;
    for(int i = 1; i <= n; i++)
    {
        v.push_back(distante[i]);
    }
    sort(v.begin(), v.end());
    out << v[v.size() - 1] + v[v.size() - 2] + 1;
    return 0;
}