Cod sursa(job #2203578)

Utilizator Menage_a_011UPB Cheseli Neatu Popescu Menage_a_011 Data 12 mai 2018 18:06:37
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.97 kb
// https://goo.gl/fBmFxu
#include <bits/stdc++.h>

using namespace std;

#define NMAX        100009
#define MMAX        200009
#define kInf        (1 << 30)
#define kInfLL      (1LL << 60)
#define kMod        666013
#define edge pair<int, int>

#define USE_FILES "MLC"

#ifdef USE_FILES
#define cin fin
#define cout fout
ifstream fin("darb.in");
ofstream fout("darb.out");
#endif

// number of tests from "in"
int test_cnt = 1;
void clean_test();

// your global variables are here


// your solution is here
vector<int>G[NMAX];
vector<int> d;
int grad[NMAX];

int n, m, start;

void BFS(int start, vector<int>&d) {
    for (int i = 1; i <= n; ++i) {
        d[i] = kInf;
    }

    queue<int>q;
    q.push(start);
    d[start] = 1;
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        for (auto &x : G[node]) {
            if (d[node] + 1 < d[x]) {
                d[x] = d[node] + 1;
                q.push(x);
            }
        }
    }

    for (int i = 1; i <= n; ++i) {
        if (d[i] == kInf) {
            d[i] = -1;
        }
    }

}

void solve() {

    cin >> n;

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

    int root;
    for (int i = 1; i <= n; ++i) {
        if (grad[i] == 0) {
            root = i;
        }
    }
    d.resize(n + 1);

    BFS(root, d);

    int Max = 0, node = 0;
    for (int i = 1; i <= n; ++i) {
        if (Max < d[i]) {
            Max = d[i];
            node = i;
        }
    }

    BFS(node, d);

    Max = 0;
    for (int i = 1; i <= n; ++i) {
        if (Max < d[i]) {
            Max = d[i];
        }
    }

    cout << Max << "\n";
    if (test_cnt > 0) {
        clean_test();
    }
}


void clean_test() {
    // clean if needed
    for (int i = 1; i <= n; ++i) {
        G[i].clear();
    }
    d.clear();
}

int main() {

//     cin >> test_cnt;

    while (test_cnt--) {
        solve();
    }

    return 0;
}