Cod sursa(job #2147591)

Utilizator sebistetuCucolas Sebastian sebistetu Data 28 februarie 2018 20:44:22
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include<fstream>
#include<list>
#include<bitset>

using namespace std;

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

const int Nmax = 100005;

list<int>Graf[Nmax];
bitset<Nmax>Vizitat;

int NrNoduri, Node, Nivel[Nmax];

inline void Citire(){

    f >> NrNoduri;

    int nod1, nod2;

    while(f >> nod1 >> nod2){

        Graf[nod1].push_back(nod2);
        Graf[nod2].push_back(nod1);
    }
}

inline void DFS(int NodCurent){

    list<int>::iterator It;

    Vizitat[NodCurent] = true;

    for(It = Graf[NodCurent].begin(); It != Graf[NodCurent].end(); ++It)
        if(!Vizitat[*It]){

            Vizitat[*It] = true;
            Nivel[*It] = 1 + Nivel[NodCurent];
            DFS(*It);
        }
}

int main(){

    Citire();
    DFS(1);

    int Index, Maxi = -1, Indice;
    for(Index = 1; Index <= NrNoduri; ++Index)
        if(Nivel[Index] > Maxi)
            Maxi = Nivel[Index], Indice = Index;

    for(Index = 1; Index <= NrNoduri; ++Index)
        Vizitat[Index] = Nivel[Index] = 0;

    DFS(Indice);

    Maxi = -1, Indice;
    for(Index = 1; Index <= NrNoduri; ++Index)
        if(Nivel[Index] > Maxi)
            Maxi = Nivel[Index], Indice = Index;

    g << Maxi + 1;
}