Cod sursa(job #2913442)

Utilizator and_Turcu Andrei and_ Data 14 iulie 2022 15:48:08
Problema Diametrul unui arbore Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.89 kb
#include <bits/stdc++.h>
#define N 100007
using namespace std;

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

int n;
int ma=-1;
int nod;
vector<int>a[N];
int vizitat[N];

void Citire()
{
    fin >> n;
    int x,y;
    while(fin >> x >>y)
    {
        a[x].push_back(y);
        a[y].push_back(x);
    }
    fin.close();
}

void BFS(int x)
{
    queue<int>q;
    q.push(x);
    vizitat[x]=1;
    while(!q.empty())
    {
        int cur=q.front();
        q.pop();
        for(auto i:a[cur])
            if( !vizitat[i] )
            {
                vizitat[i]=1+vizitat[cur];
                q.push(i);
            }
    }
    for(int i=1;i<=n;i++)
        if(ma < vizitat[i])
        {
            ma=max(ma,vizitat[i]);
            nod=i;
        }
}

int main()
{
    Citire();
    BFS(1);
    for(int i=0;i<=n;i++)
        vizitat[i]=0;
    BFS(nod);
    fout << nod << " ";
    return 0;
}