Cod sursa(job #2862813)

Utilizator david.kerekesKerekes David david.kerekes Data 5 martie 2022 21:16:35
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.32 kb
#include <iostream>
#include <fstream>
#include <list>
using namespace std;

int n;
list<int> szomsz[100001];
list<int>::iterator it;
int jart[100001];
int d[100001];
int elso,utolso;

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 Inddmaxi()
{
    int maxi=0,maxiInd=0;
    for(int i=1;i<=n;i++)
    {
        if(d[i]>maxi)
        {
            maxiInd=i;
            maxi=d[i];
        }
    }
    return maxiInd;
}

void szelessegiBejaras(int kezdocsucs)
{
    int sor[n+1]={0};
    fill_n(d,n+1,1);
    fill_n(jart,n+1,false);
    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(Inddmaxi());
    ofstream fout("darb.out");
    int maxi=0;
    for(int i=1;i<=n;i++)
    {
        if(d[i]>maxi)
        {
            maxi=d[i];
        }
    }
    fout<<maxi;
    return 0;
}