Cod sursa(job #2986330)

Utilizator Radu_TudorRadu Tudor Radu_Tudor Data 28 februarie 2023 11:50:32
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.34 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_node;
int max_dist;

void 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 dfs1(int node, int father, int dist[]) {

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

    if (dist[node] > max_dist)
        max_node = node,
        max_dist = dist[node];

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

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

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

    if (dist[node] > max_dist)
        max_dist = dist[node];

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

void solve() {

    dfs1(1, 0, dist1);
    dfs2(max_node, 0, dist2);
}

void display() {

    fout << max_dist;
}

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

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

    return 0;
}