Cod sursa(job #1705192)

Utilizator morris18cmDumnezeu morris18cm Data 20 mai 2016 00:44:48
Problema Diametrul unui arbore Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <time.h>
#include <stdlib.h>

using namespace std;

struct node{
    vector<int> fii;
}arbore[100005];

int n, x, y, frunza, lungime=0;

void DFS(int i, int distanta)
{
    if( arbore[i].fii.size() ){
        lungime++;
        for(int j=0; j<arbore[i].fii.size(); j++){
            DFS(arbore[i].fii[j], distanta+1);
        }
    }else{
        if(distanta>lungime){
            frunza=i;
            lungime=distanta;
        }
    }
}

int cauta_nod_nefrunza(){
    for(int i = 1; i<=n; i++)
        if(arbore[i].fii.size())
            return i;
}

int main()
{
    ifstream f ("darb.in");
    ofstream g ("darb.out");
    f>>n;
    while(f>>x>>y)
        arbore[x].fii.push_back(y);
    //srand (time(NULL));
    DFS(cauta_nod_nefrunza() , 1);
    DFS(frunza, 1);
    cout<<lungime;
    g<<lungime;
    return 0;
}