Cod sursa(job #3281253)

Utilizator PitigoiOlteanEmanuelPitigoi Oltean Emanuel PitigoiOlteanEmanuel Data 28 februarie 2025 19:16:35
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.55 kb
#include <fstream>
#include <queue>
#define float double
using namespace std;
ifstream cin("darb.in");
ofstream cout("darb.out");

struct per
{
    vector <int> dest;

}v[100005];
int dr[100005],dr1[100005];

int Max=0,rez,n,m;

int bfs()
{
    queue <int> q;
    q.push(1);
    dr[1]=1;
    while(!q.empty())
    {
        int nod=q.front();
        q.pop();
        for(int i=0;i<v[nod].dest.size();i++)
        {
            int aj=v[nod].dest[i];
            if(dr[aj]==0)
            {
                dr[aj]=dr[nod]+1;
                q.push(aj);
                if(Max<dr[aj])
                {
                    Max=dr[aj];
                    rez=aj;
                }
            }
        }
    }
    return 0;

}



int gf()
{
    queue <int> q;
    q.push(rez);
    dr1[rez]=1;
    Max=0;
    while(!q.empty())
    {
         int nod=q.front();
        q.pop();
        for(int i=0;i<v[nod].dest.size();i++)
        {
            int aj=v[nod].dest[i];
            if(dr1[aj]==0)
            {
                dr1[aj]=dr1[nod]+1;
                q.push(aj);
                if(Max<dr1[aj])
                {
                    Max=dr1[aj];
                    rez=aj;
                }
            }
    }
    }
    return 0;
}




int main()
{
    cin>>n;
    m=n-1;
    for(int i=1;i<=m;i++)
    {
    int a,b;
        cin>>a>>b;
            //r[b]=1;
        v[a].dest.push_back(b);
        v[b].dest.push_back(a);
    }
    bfs();
    gf();
    cout<<Max;


    return 0;
}