Cod sursa(job #2780705)

Utilizator betybety bety bety Data 7 octombrie 2021 18:45:55
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.94 kb
#include <bits/stdc++.h>
using namespace std;
ifstream in("darb.in");
ofstream out("darb.out");
const int lim=1e5+4;
queue<pair<int,int> > q;
vector<int> vec[lim];
bool ok[lim];
int n,x,y,d;
int main()
{
    in>>n;
    for(int i=1;i<n;++i)
        in>>x>>y,
        vec[x].push_back(y),
        vec[y].push_back(x);
    int cap,dist;
    q.push({1,0});
    ok[1]=true;
    while(!q.empty())
    {
        int nod=q.front().first;
        int d=q.front().second; q.pop();
        cap=nod, dist=d;
        for(int x:vec[nod])
        if(!ok[x]) ok[x]=true,
            q.push({x,d+1});
    }
    memset(ok,0,sizeof(ok));
    q.push({cap,0});
    ok[cap]=true;
    while(!q.empty())
    {
        int nod=q.front().first;
        int d=q.front().second; q.pop();
        cap=nod, dist=d;
        for(int x:vec[nod])
        if(!ok[x]) ok[x]=true,
            q.push({x,d+1});
    }
    out<<dist+1<<'\n';
    return 0;
}