Cod sursa(job #2811567)

Utilizator linte_robertLinte Robert linte_robert Data 2 decembrie 2021 17:02:25
Problema Diametrul unui arbore Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.35 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <deque>
#include <utility>
#include <queue>
using namespace std;

int N;

vector < vector < int > > g;
vector < int > dist;
vector < int > viz;

void dfs(int x, int d){
    viz[x] = 1;
    dist[x] = d;
        for( auto n : g[x] ){
            if( viz[n] == 0 ){
                dfs(n, d+1);
            }
        }
}

pair < int, int > getMaxDist(){
    int distMax = 0;
    int nod = 0;
    for( int i = 1; i <=N; i++ ){
        if( dist[i] > distMax ){
            distMax = dist[i];
            nod = i;
        }
    }
    return make_pair(distMax, nod);
}

void clear(){
    for( int i = 1; i <=N; i++ ){
        viz[i] = 0;
        dist[i] = 0;
    }
}

int main(){
    ifstream fin("darb.in");
    ofstream fout("darb.out");
    fin >> N;
    for(int i = 0; i <= N; i++){
        vector < int > v;
        g.push_back(v);
    }
    for( int i = 0; i < N-1; i++ ){
        int intrare, iesire;
        fin >> intrare >> iesire;
        g[intrare].push_back(iesire);
        g[iesire].push_back(intrare);
    }
    dist.resize(N+1);
    viz.resize(N+1);
    dfs(1,0);
    pair<int,int> maxAndNod = getMaxDist();
    clear();
    int n1 = maxAndNod.second;
    dfs(maxAndNod.second,0);
    maxAndNod = getMaxDist();
    fout << maxAndNod.second;
}