Cod sursa(job #2778143)

Utilizator andcovAndrei Covaci andcov Data 29 septembrie 2021 09:25:49
Problema Diametrul unui arbore Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.08 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <unordered_map>

using namespace std;

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

int n;
unordered_map<int, vector<int>> adj;
bool vis[100001];

void read() {
    int a, b;

    in >> n;

    for(int i = 0; i < n - 1; ++i) {
        in >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
}

pair<int, int> dfs(int no, int len) {
    if(vis[no]) {
        return make_pair(len, no);
    }

    vis[no] = true;
    len++;

    int maxv = len, maxn = no;
    for(auto e : adj[no]) {
        auto aux = dfs(e, len);
        int l = aux.first, nd = aux.second;
        if(l > maxv) {
            maxv = l;
            maxn = nd;
        }
    }

    return make_pair(maxv, maxn);
}

int solve() {
    for(int i = 0; i <= n; ++i) {
        vis[i] = false;
    }
    int f = dfs(1, 0).second;

    for(int i = 0; i <= n; ++i) {
        vis[i] = false;
    }
    return dfs(f, 0).first;
}

int main()
{
    read();
    out << solve();
    return 0;
}