Cod sursa(job #2683315)

Utilizator andrei.florea0405Florea Andrei-Bogdan andrei.florea0405 Data 10 decembrie 2020 21:42:00
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 kb
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define MOD 1000000007

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef double ld;

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

vi A[100010];
int visited[100010];

void dfs(int node, int dist_crt, int &dist, int &farthest) {
    visited[node] = 1;

    if (dist_crt > dist) {
        dist = dist_crt;
        farthest = node;
    }

    for (auto &it : A[node]) {
        if (!visited[it]) {
            dfs(it, dist_crt + 1, dist, farthest);
        }
    }
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n;
    fin >> n;

    for (int i = 1; i < n; i++) {
        int x, y;
        fin >> x >> y;
        A[x].pb(y);
        A[y].pb(x);
    }
    
    int dist = 0;
    int startNode = 0;
    dfs(1, 0, dist, startNode);

    memset(visited, 0, sizeof(visited));

    dist = 0;
    int randomNode = 0;
    dfs(startNode, 0, dist, randomNode);
    
    fout << dist + 1 << "\n";

    return 0;
}