Cod sursa(job #2191678)

Utilizator TooHappyMarchitan Teodor TooHappy Data 3 aprilie 2018 13:37:43
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include <bits/stdc++.h>
using namespace std;
     
ifstream in("darb.in");
ofstream out("darb.out");

const int NMax = 1e5 + 5;

vector< int > G[NMax];

pair< int, int > DFS(int node, int father) {
    pair< int , int > ans(node, 0);

    for(auto vecin: G[node]) {
        if(vecin == father) {
            continue;
        }

        pair< int, int > aux = DFS(vecin, node);
        if(aux.second + 1 > ans.second) {
            ans.second = aux.second + 1;
            ans.first = aux.first;
        }
    }

    return ans;
}

int main() {
    ios::sync_with_stdio(false); in.tie(0); out.tie(0);

    int n; in >> n;
    for(int i = 1; i < n; ++i) {
        int x, y; in >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }

    pair< int, int > frunza = DFS(1, 1);
    out << DFS(frunza.first, 0).second + 1 << '\n';

    in.close(); out.close();
     
    return 0;
}