Cod sursa(job #3262885)

Utilizator victordugVictor Dughie victordug Data 11 decembrie 2024 21:03:05
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.21 kb
#include <bits/stdc++.h>

using namespace std;

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

const int Nmx = 100001;
int n;
vector <int> ad[Nmx];
vector <int> frz;
queue<int> q;
int dis[Nmx];
bool vis[Nmx], cond;

void BFS(int nod, bool par)
{
    q.push(nod);
    vis[nod]=1;
    dis[nod] = 1;
    while(!q.empty())
    {
        nod=q.front();
        q.pop();
        cond=0;
        for(auto& z: ad[nod])
        {
            if(vis[z] == 0)
            {
                cond=1;
                q.push(z);
                vis[z]=1;
                dis[z]= dis[nod] + 1;
            }
        }
        if(par==1)if(cond==0)frz.push_back(nod);
    }
}
int main()
{
    int x, y, frmx=-1, dfrmx=-1, dmax=-1;
    fin >> n;
    for(int i=1;i<n;i++)
    {
        fin >> x >> y;
        ad[x].push_back(y);
        ad[y].push_back(x);
    }
    BFS(x,1);
    for(auto& z: frz)
    {
        if(dis[z]>dfrmx)
        {
            dfrmx=dis[z];
            frmx=z;
        }
    }
    for(int i=1;i<=Nmx;i++)
    {
        vis[i]=0;
        dis[i]=0;
    }
    BFS(frmx, 0);
    for(auto& z: frz)
    {
        if(dis[z]>dmax)dmax=dis[z];
    }
    fout << dmax;
}