Cod sursa(job #2671904)

Utilizator antonioganea3Antonio Ganea antonioganea3 Data 12 noiembrie 2020 19:52:42
Problema Diametrul unui arbore Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.08 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <string.h>
using namespace std;

#define MAX_N 1000002

vector<int> links[MAX_N];
queue<int> q;

int n;
int contor[MAX_N];
int visited[MAX_N];
int last;

int D;

void dfs_first( int node, int dist ){
    visited[node] = true;
    for ( auto &x : links[node] ){
        if ( ! visited[x] ){
            dfs_first(x, dist+1);
        }
    }
    if ( dist > D ){
        D = dist;
        last = node;
    }
}

int visited2[MAX_N];
int answer = 0;
void dfs( int node, int dist ) {
    visited2[node] = 1;
    if ( dist > answer )
        answer = dist;

    for ( auto &x : links[node] ){
        if ( visited2[x] == 0)
            dfs(x, dist+1);
    }
}

int main()
{
    ifstream fin("darb.in");
    ofstream fout("darb.out");

    fin >> n;

    int a, b;
    for ( int i = 0; i < n - 1; i++ ) {
        fin >> a >> b;
        links[a].push_back(b);
        links[b].push_back(a);
    }

    dfs_first(1, 1);
    dfs(last,1);
    fout << answer;
    return 0;

}