Cod sursa(job #1206447)

Utilizator MaarcellKurt Godel Maarcell Data 9 iulie 2014 23:39:24
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include <fstream>
#include <vector>
#include <string.h>
using namespace std;

int N,diam,niv,aux; vector<int> graf[100100]; bool viz[100100];
void dfs1(int nod, int nivel){
    if (!viz[nod]){
        viz[nod]=1;
        if (nivel>niv) {niv=nivel; aux=nod;}
        for (int i=0; i<graf[nod].size(); i++)
            dfs1(graf[nod][i],nivel+1);
    }
}
void dfs2(int nod, int nivel){
    if (viz[nod]){
        viz[nod]=0;
        if (nivel>diam) diam = nivel;
        for (int i=0; i<graf[nod].size(); i++)
            dfs2(graf[nod][i],nivel+1);
    }
}
int main(){
    ifstream in("darb.in");
    ofstream out("darb.out");
    in >> N;
    int i,x,y;
    for (i=1; i<N; i++){
        in >> x >> y;
        graf[x].push_back(y);
        graf[y].push_back(x);
    }
    aux=niv=diam=0;
    dfs1(1,0);
    dfs2(aux,1);
    out << diam;
    return 0;
}