Cod sursa(job #2862762)

Utilizator david.kerekesKerekes David david.kerekes Data 5 martie 2022 20:06:46
Problema Diametrul unui arbore Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.11 kb
#include <iostream>
#include <fstream>
#include <list>
using namespace std;

int n;
list<int> szomsz[100001];
list<int>::iterator it;
int jart[100001]={0};
int d[100001]={0};
int elso=1,utolso=1;

void beolvas()
{
    ifstream f("darb.in");
    f>>n;
    int a,b;
    while(f>>a>>b)
    {
        szomsz[a].push_back(b);
        szomsz[b].push_back(a);
    }
    f.close();
}

int dmaxi()
{
    int maxi=0;
    for(int i=1;i<=n;i++)
    {
        if(d[i]>maxi)
            maxi=i;
    }
    return maxi;
}

void szelessegiBejaras(int kezdocsucs)
{
    int sor[n+1]={0};
    elso=1;
    utolso=1;
    jart[kezdocsucs]=1;
    sor[elso]=kezdocsucs;
    while(elso<=utolso)
    {
        for(it=szomsz[sor[elso]].begin();it!=szomsz[sor[elso]].end();it++)
        {
            if(!jart[*it])
            {
                jart[*it]=1;
                utolso++;
                sor[utolso]=*it;
                d[*it]=d[sor[elso]]+1;
            }
        }
        elso++;
    }
}


int main()
{
    beolvas();
    szelessegiBejaras(1);
    szelessegiBejaras(dmaxi());
    ofstream fout("darb.out");
    cout<<dmaxi()<<endl;
    return 0;
}