Cod sursa(job #3248612)

Utilizator devilexeHosu George-Bogdan devilexe Data 12 octombrie 2024 11:19:00
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#include <bits/stdc++.h>
using namespace std;

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

const int MAXN = 1e5;
vector<int> G[MAXN + 1];
vector<int> dist;
int max_dist_node = 0;
int n1 = 1;
int N;

void dfs(int n)
{
    for (const int &x : G[n])
    {
        if (x == n1)
            continue;
        if (!dist[x])
        {
            dist[x] = dist[n] + 1;
            if (dist[x] > dist[max_dist_node])
            {
                max_dist_node = x;
            }
            dfs(x);
        }
    }
}

int main()
{
    fin >> N;
    int a, b;
    for (int m = 1; m < N; m++)
    {
        fin >> a >> b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    dist = vector<int>(N + 1);
    n1 = 1;
    dfs(1);
    // cout << "N1: " << max_dist_node << endl;
    dist = vector<int>(N + 1);
    n1 = max_dist_node;
    dfs(n1);
    // cout << "N2: " << max_dist_node << endl;
    fout << dist[max_dist_node] + 1;
    return 0;
}