Cod sursa(job #1401825)

Utilizator irimiecIrimie Catalin irimiec Data 26 martie 2015 10:06:44
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.55 kb
#include <bits/stdc++.h>

using namespace std;

#define     mp              make_pair
#define     fs              first
#define     sc              second
#define     pob             pop_back
#define     pub             push_back
#define     eps             1E-7
#define     sz(a)           a.size()
#define     count_one       __builtin_popcount;
#define     count_onell     __builtin_popcountll;
#define     fastIO          ios_base::sync_with_stdio(false)
#define     PI              (acos(-1.0))
#define     linf            (1LL<<62)//>4e18
#define     inf             (0x7f7f7f7f)//>2e9

#define MAXN 100010

int n;
vector<int> vec[MAXN];
bitset<MAXN> viz;
int maxlen, maxnod;

void read() {
    #ifndef ONLINE_JUDGE
    freopen("darb.in", "r", stdin);
    freopen("darb.out", "w", stdout);
    #endif

    int x, y;

	scanf("%d", &n);
	while(n--) {
        scanf("%d%d", &x, &y);
        vec[x].pub(y);
        vec[y].pub(x);
	}
}

void bfs(int root) {
    queue<pair<int, int> > Q;
    viz.reset();
    maxlen = 0;
    maxnod = 0;

    int nod, clen;
    for(Q.push(mp(root, 1)), viz[root] = true; !Q.empty(); Q.pop()) {
        nod = Q.front().fs; clen = Q.front().sc;
        if(clen > maxlen)
            maxlen = clen,
            maxnod = nod;

        for(auto it : vec[nod]) if(!viz[it]){
            viz[it] = true;
            Q.push(mp(it, clen + 1));
        }
    }
}

void solve() {
    bfs(1);
    bfs(maxnod);
    printf("%d\n", maxlen);
}

int main() {
	read();
    solve();

    return 0;
}