Cod sursa(job #2624460)

Utilizator loraclorac lorac lorac Data 4 iunie 2020 21:03:19
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.81 kb
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream cin("darb.in");
ofstream cout("darb.out");
const int lim=1e5+3;
vector<int> vec[lim];
int n,src,x,y,fin,diam;
bool ok[lim];
int d[lim];
queue<int> q;
void bf()
{
    q.push(src);
    ok[src]=d[src]=1;
    diam=0;
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        if(d[x]>diam)
            diam=d[x],fin=x;
        for(auto y:vec[x])
        if(ok[y]==0)
            ok[y]=1,d[y]=d[x]+1,q.push(y);
    }
}
int main()
{
    cin>>n;
    for(int i=1;i<n;++i)
    {
        cin>>x>>y;
        vec[x].push_back(y);
        vec[y].push_back(x);
    }
    src=1;
    bf();
    src=fin;
    for(int i=1;i<=n;++i)
        ok[i]=d[i]=0;
    bf();
    cout<<diam<<'\n';
    return 0;
}