Cod sursa(job #1594050)

Utilizator bullseYeIacob Sergiu bullseYe Data 9 februarie 2016 09:54:14
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <cstdio>
#include <vector>
#define NMAX 100010
using namespace std;

vector <int> L[NMAX];
bool viz[NMAX];
int n, last, daux, diametru;

void citire();
int diametru_arbore();
void DFS (int);
void afisare(int);

int main(){
    citire();
    afisare(diametru_arbore());
    return 0;
}

void citire(){
    FILE*fin=fopen("darb.in", "r");
    fscanf(fin, "%d", &n);
    int i, a, b;
    for (i=1; i<n; ++i){
        fscanf(fin, "%d %d", &a, &b);
        L[a].push_back(b);
        L[b].push_back(a);
    }
    fclose(fin);
    return;
}

int diametru_arbore(){
    int i;
    DFS (1);
    daux=diametru=0;
    for (i=1; i<=n; ++i) viz[i]=false;
    DFS (last);
    return diametru;
}

void DFS (int vf)
{
    int i;
    ++daux; viz[vf]=true;
    if (diametru<daux){
        diametru=daux; last=vf;
    }

    for (i=0; i<L[vf].size(); ++i)
        if (!viz[L[vf][i]])
            DFS (L[vf][i]);
    --daux;
}

void afisare (int rez)
{
    FILE*fout=fopen ("darb.out", "w");
    fprintf(fout, "%d\n", rez);
    fclose(fout);
    return;
}