Cod sursa(job #1180441)

Utilizator oprea1si2si3Oprea Sebastian oprea1si2si3 Data 30 aprilie 2014 17:45:25
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include<fstream>
#include<iostream>
#include<vector>
using namespace std;

int N,sol,rad;
bool viz[100010];
vector <int> Muchie[100010];

void citire() {

    ifstream in("darb.in");
    int i,x,y;
    in>>N;
    for(i=1;i<N;i++) {
        in>>x>>y;
        Muchie[x].push_back(y);
        Muchie[y].push_back(x);
    }
    in.close();

}

void Dfs(int nod,int adancime) {

    int i,vecin;
    viz[nod]=1;
    if(adancime>sol) {
        sol=adancime;
        rad=nod;
    }
    for(i=0;i<Muchie[nod].size();i++) {
        vecin=Muchie[nod][i];
        if(!viz[vecin])
            Dfs(vecin,adancime+1);
    }

}
void Dfs1(int nod,int adancime) {

    int i,vecin;
    viz[nod]=0;
    if(adancime>sol)
        sol=adancime;
    for(i=0;i<Muchie[nod].size();i++) {
        vecin=Muchie[nod][i];
        if(viz[vecin]==1)
            Dfs1(vecin,adancime+1);
    }

}

void solve() {

    Dfs(1,1);
    sol=0;
    Dfs1(rad,1);

}

void afisare() {

    ofstream out("darb.out");
    out<<sol<<'\n';
    out.close();

}


int main() {

    citire();
    solve();
    afisare();
    return 0;

}