Cod sursa(job #2671274)

Utilizator dariahazaparuHazaparu Daria dariahazaparu Data 11 noiembrie 2020 20:50:54
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.87 kb
#include <iostream>
#include <fstream>
#include <vector>
const int N_MAX = 100005;

std :: vector <int> graph[N_MAX];
bool vis[N_MAX];
int n, m;
int dist[N_MAX];
int dist_maxim;

void dfs( int node) {
//    fout << node << " ";
    vis[node] = true;
    for (int i : graph[node]) {
        if (!vis[i]) {
            dist[i] = dist[node] + 1;
            if (dist[i] > dist[dist_maxim])
                dist_maxim = i;
            dfs(i);
        }
    }
}

int main() {

    std :: ifstream fin ("darb.in");
    std :: ofstream fout ("darb.out");

    fin >> n;
    for (int i = 1; i < n; ++i) {
        int a, b;
        fin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    dfs(1);
    // reset
    for (int i = 1; i <= n; ++i) {
        dist[i] = 0;
        vis[i] = false;
    }
    dfs(dist_maxim);

    fout << dist[dist_maxim] + 1;
    return 0;
}