Cod sursa(job #2844846)

Utilizator VladOSBVlad Oleksik VladOSB Data 5 februarie 2022 18:18:05
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.33 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

int niv[100002],n;
//int t[100002]
vector <vector <int> > a;

int bfs(int start)
{
    queue <int> q;
    int curent,i,nivmax=-1,nodmax;
    bool viz[100002];
    for(i=1;i<=n;i++)
    {
        viz[i]=0;
    }
    q.push(start);
    niv[start]=0;
    while(!q.empty())
    {
        curent=q.front();
        q.pop();
        viz[curent]=1;
        for(int x : a[curent])
        {
            if(!viz[x])
            {
                niv[x]=niv[curent]+1;
                q.push(x);
            }
        }
    }
    for(i=1;i<=n;i++)
    {
        if(niv[i]>nivmax)
        {
            nivmax=niv[i];
            nodmax=i;
        }
    }
    return nodmax;
}

int main()
{
    int i,x,y;
    in >> n;
    a.resize(n+2);
    for(i=0;i<=n;i++)
    {
        a[i].resize(0);
    }
    while(in >> x >> y)
    {
        a[x].push_back(y);
        a[y].push_back(x);
        //t[y]=x;
    }
    x=bfs(1);
    /*for(i=1;i<=n;i++)
    {
        cout << niv[i] << ' ';
    }
    cout << '\n';*/
    y=bfs(x);
    /*cout << x;
    for(i=1;i<=n;i++)
    {
        cout << niv[i] << ' ';
    }*/
    out << niv[y]+1;
    return 0;
}