Cod sursa(job #2665379)

Utilizator Silviu.Stancioiu@gmail.comSilviu Stancioiu [email protected] Data 30 octombrie 2020 17:23:25
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.85 kb
#include <fstream>
#include <vector>

#define MAX_N 100005

using namespace std;
ifstream fin("darb.in");
ofstream fout("darb.out");
int n;
vector<int> tree_graph[MAX_N];
int max_dist = 0;
int max_node = 0;
int viz[MAX_N];

void dfs(const int node, const int viz_nr, const int dist)
{
    if (viz[node] == viz_nr)
        return;

    viz[node] = viz_nr;
    if (dist > max_dist)
    {
        max_dist = dist;
        max_node = node;
    }

    for (auto neigh : tree_graph[node])
        dfs(neigh, viz_nr, dist + 1);
}

int main()
{
    fin >> n;

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

    dfs(0, 1, 1);
    dfs(max_node, 2, 1);

    fout << max_dist;

    return 0;
}