Cod sursa(job #2408964)

Utilizator Leonard123Mirt Leonard Leonard123 Data 18 aprilie 2019 15:43:47
Problema Diametrul unui arbore Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.1 kb
#include <fstream>
#include <vector>
#define maxn 100005
using namespace std;
vector <int> V[maxn];

ifstream cin("darb.in");
ofstream cout("darb.out");

int lista[maxn],nr[maxn],n,x,y,nod,verificat[maxn],distanta;

void read(){
    cin>>x>>y;
    V[x].push_back(y);
    nr[x]++;
    V[y].push_back(x);
    nr[y]++;
}

void dfs(){
    distanta++;
    int ok=0;
    for(int i=0; i<nr[nod]&&ok==0; i++)
        if(verificat[V[nod][i]]==1){
            nod=V[nod][i];
            verificat[nod]=0;
            ok=1;
        }
    if(ok==0)
        return;
    dfs();
}

void bfs(){
        int ultim=1;
        lista[1]=1;
        verificat[1]=1;
        for(int prim=1; prim<=ultim; prim++)
            for(int j=0; j<nr[lista[prim]]; j++)
                if(verificat[V[prim][j]]==0){
                    verificat[V[prim][j]]=1;
                    lista[++ultim]=V[prim][j];
                }
        nod=lista[ultim];
        verificat[nod]=0;
}
int main()
{
    cin>>n;
    for(int i=1; i<n; i++)
        read();
    bfs();
    dfs();
    cout<<distanta;
    return 0;
}