Cod sursa(job #2861591)

Utilizator david.kerekesKerekes David david.kerekes Data 4 martie 2022 09:44:04
Problema Diametrul unui arbore Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.43 kb
#include <iostream>
#include <fstream>
#include <list>
using namespace std;

int n;
list<int> szomsz[100000];
list<int>::iterator it;
int jart[100000]={0};
int d[100000]={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(int i=1;i<=n;i++)
        {
            if(szomsz[sor[elso]][i]&&!jart[i])
            {
                jart[i]=1;
                utolso++;
                sor[utolso]=i;
                d[i]=d[sor[elso]]+1;
            }
        }*/
        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");
    fout<<dmaxi()<<endl;
    return 0;
}