Cod sursa(job #2225099)

Utilizator AlexPop28Pop Alex-Nicolae AlexPop28 Data 25 iulie 2018 21:44:09
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include <bits/stdc++.h>
#define all(cont) cont.begin(), cont.end()
#define pb push_back
#define fi first
#define se second

using namespace std;

typedef pair <int, int> pii;
typedef vector <int> vi;
typedef long long ll;
typedef unsigned long long ull;

ifstream f ("darb.in");
ofstream g ("darb.out");

const int NMAX = 1e5;
vi adj[NMAX];
int dist[NMAX];

void dfs (int node, int dad) {
    for (auto &i : adj[node]) {
        if (i == dad) continue;
        dist[i] = dist[node] + 1;
        dfs (i, node);
    }
}

int main() {
    int n;
    f >> n;
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        f >> u >> v;
        --u; --v;
        adj[u].pb (v);
        adj[v].pb (u);
    }
    dist[0] = 1;
    dfs (0, - 1);
    int maxx = -1;
    int start = 0;
    for (int i = 0; i < n; ++i) {
        if (dist[i] > maxx) {
            maxx = dist[i];
            start = i;
        }
    }
    memset (dist, 0, sizeof (dist));
    dist[start] = 1;
    dfs (start, -1);
    maxx = -1;
    for (int i = 0; i < n; ++i) {
        maxx = max (maxx, dist[i]);
    }
    g << maxx << '\n';
}