Cod sursa(job #2671368)

Utilizator QubeeStefan Ste Qubee Data 11 noiembrie 2020 23:03:01
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.84 kb
#include <fstream>
#include <vector>

using namespace std;

ifstream f("darb.in");
ofstream g("darb.out");

int n;
int nodmaxx, maxi;

vector < int > graf[100001];
vector < bool > viz;

void citire(){

    f >> n;

    for(int i = 1; i <= n - 1; i++){

        int a, b;

        f>> a >> b;

        graf[a].push_back(b);
        graf[b].push_back(a);
    }

}


void DFS(int k, int diametru){

    viz[k] = 1;

    if(diametru > maxi){
        maxi = diametru;
        nodmaxx = k;
    }

    for(int i = 0; i < graf[k].size(); i++){

        if(viz[graf[k][i]] == 0)
            DFS(graf[k][i], diametru + 1);

    }

}


int main(){
    citire();

    viz = vector < bool > (n + 1, 0);
    DFS(1, 0);

    viz = vector < bool > (n + 1, 0);
    DFS(nodmaxx, 0);

    g << maxi + 1;

    return 0;
}