Cod sursa(job #3250046)

Utilizator IleaIlea Bogdan Ilea Data 19 octombrie 2024 09:46:35
Problema Diametrul unui arbore Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.78 kb
#include <bits/stdc++.h>

using namespace std;

string file="darb";
ifstream fin(file+".in");
ofstream fout(file+".out");

set<int> g[100001];
vector<int> b;
void bfs(int i)
{
    queue<int> q;
    q.push(i);
    b[i]=1;
    while (!q.empty()){
        i=q.front();
        q.pop();
        for (auto j:g[i]){
            if (!b[j]){
                q.push(j);
                b[j]=b[i]+1;
            }
        }
    }
}
int main()
{
    int n;
    fin>>n;
    b.resize(n+1);
    int x, y;
    while(fin>>x>>y){
        g[x].insert(y), g[y].insert(x);
    }
    bfs(1);
    int max1=0, max2=0;
    for (int i=1; i<=n; i++){
        if (max1<=b[i]){
            max2=max1;
            max1=b[i];
        }
    }
    fout<<max1+max2-1;
    return 0;
}