Cod sursa(job #2723608)

Utilizator AACthAirinei Andrei Cristian AACth Data 15 martie 2021 09:14:55
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.22 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f("darb.in");
ofstream g("darb.out");
#define int long long
const int Max = 1e5+1;
void nos()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
}
int n;

vector < int > v[Max];
struct ans{
    int nod;
    int len;
};
ans bfs(int nod)
{
    int len[Max] = {};
    queue < int > c;
    c.push(nod);
    ans sol;
    sol.len = 0;
    while(!c.empty())
    {
        int nod = c.front();
        c.pop();
        for(int dest :v[nod])
            if(len[dest] == 0)
        {
            len[dest] = len[nod] + 1;
            if(len[dest] > sol.len)
                sol={dest,len[dest]};
            c.push(dest);
        }
    }
    return sol;
}
void read()
{
    f>>n;
    int i;
    for(i=1;i<n;i++)
    {
        int n1,n2;
        f>>n1>>n2;
        v[n1].push_back(n2);
        v[n2].push_back(n1);
    }
}
void solve()
{
    int i;
    for(i=1;i<=n;i++)
        if(v[i].size() == 1)
    {
        //leaf
        ans this_ans = bfs(i);
        ans final_ans = bfs(this_ans.nod);
        g<<final_ans.len + 1;
        break;
    }

}

int32_t main()
{
    nos();
    read();
    solve();
    return 0;
}