Cod sursa(job #1551076)

Utilizator BlueStrutAndrei Prahoveanu BlueStrut Data 15 decembrie 2015 08:39:04
Problema Diametrul unui arbore Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include<cstdio>
#include<vector>
#include<deque>
using namespace std;
vector<int> a[100002];
vector<int>::iterator it;
deque<int> cd, cd2;
int i, n, x, y, mx=1, sel[100002];
bool ok;
int main(){
    freopen("darb.in","r",stdin);
    freopen("darb.out","w",stdout);
    scanf("%d", &n);
    for (i=1;i<n;i++) {scanf("%d%d", &x, &y); a[x].push_back(y); a[y].push_back(x);sel[i+1]=0;}
    cd2.push_back(1); sel[1]=0; ok=true;
    while (ok) {
        ok=false; cd.swap(cd2); cd2.clear();
        while (!cd.empty()) {
            x=cd.front(); cd.pop_front();
            for (it=a[x].begin();it!=a[x].end();it++) if (sel[*it]==0) {
                sel[*it]=999999; cd2.push_back(*it); ok=true;
            }
        }
    }
    cd2.clear();
    cd.push_back(x);
    sel[x]=1;
    while (!cd.empty()) {
        x=cd.front(); cd.pop_front();
        for (it=a[x].begin();it!=a[x].end();it++) if (sel[*it]>sel[x]+1) {
            sel[*it]=sel[x]+1; if (sel[x]+1>mx) mx=sel[x]+1;
            cd2.push_back(*it);
        }
        cd.swap(cd2); cd2.clear();
    }
    printf("%d\n", mx); return 0;
}