Cod sursa(job #2986326)

Utilizator Radu_TudorRadu Tudor Radu_Tudor Data 28 februarie 2023 11:45:22
Problema Diametrul unui arbore Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.24 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

const int N_MAX = 1e5 + 1;

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

int N;
vector<int> edges[N_MAX];

/// dfs-related
int dist1[N_MAX];
int dist2[N_MAX];

/// result
int max_dist;

int read() {

    fin >> N;

    int from, to;
    for (int i = 1; i < N; i++) {

        fin >> from >> to;

        edges[from].push_back(to);
        edges[to].push_back(from);
    }
}

void dfs(int node, int father, int dist[]) {

    dist[node] = dist[father] + 1;

    for (size_t i = 0; i < edges[node].size(); i++)
        if (edges[node][i] != father)
            dfs(edges[node][i], node, dist);
}

void solve() {

    dfs(1, 0, dist1);

    int max_node = 1;
    for (int i = 1; i <= N; i++)
        if (dist1[i] > max_dist)
            max_dist = dist1[i],
            max_node = i;

    dfs(max_node, 0, dist2);

    max_dist = 0;
    for (int i = 1; i <= N; i++)
        if (dist2[i] > max_dist)
            max_dist = dist2[i],
            max_node = i;
}

void display() {

    fout << max_dist;
}

int main()
{
    read();
    solve();
    display();

    fin.close();
    fout.close();

    return 0;
}