Cod sursa(job #2701859)

Utilizator beingsebiPopa Sebastian beingsebi Data 1 februarie 2021 23:26:31
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.96 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("darb.in");
ofstream g("darb.out");
// #define f cin
// #define g cout
int n, t, dis[100009] = {0, 1}, mx = 1, rez = 1;
vector<int> v[100009];
void dfs1(int);
void dfs2(int);
int32_t main()
{
    ios_base::sync_with_stdio(false);
    f.tie(nullptr);
    g.tie(nullptr);
    f >> n;
    for (int x, y, i = 1; i < n; i++)
        f >> x >> y, v[x].emplace_back(y), v[y].emplace_back(x);
    dfs1(1);
    memset(dis, 0, sizeof dis);
    dis[mx] = 1;
    dfs2(mx);
    g << rez;
    return 0;
}
void dfs1(int x)
{
    for (const int &i : v[x])
        if (!dis[i])
        {
            dis[i] = dis[x] + 1;
            if (dis[i] > dis[mx])
                mx = i;
            dfs1(i);
        }
}
void dfs2(int x)
{
    for (const int &i : v[x])
        if (!dis[i])
        {
            dis[i] = dis[x] + 1;
            rez = max(rez, dis[i]);
            dfs2(i);
        }
}