Cod sursa(job #1705175)

Utilizator morris18cmDumnezeu morris18cm Data 20 mai 2016 00:23:01
Problema Diametrul unui arbore Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <iostream>
#include <fstream>
#include <vector>

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()!= 0 ){
        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 main()
{
    ifstream f ("darb.in");
    ofstream g ("darb.out");
    f>>n;
    for(int i=1; i<n;i++)
    {
        f>>x>>y;
        arbore[x].fii.push_back(y);
    }
    DFS(1, 1);
    DFS(frunza, 1);
    if(n!=1)
        g<<lungime;
    else
        g<<0;
    return 0;
}