Cod sursa(job #1551126)

Utilizator BlueStrutAndrei Prahoveanu BlueStrut Data 15 decembrie 2015 10:19:58
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include<cstdio>
#include<deque>
#include<vector>
#include<cstring>
using namespace std;
vector<int> a[100001];
vector<int>::iterator it;
deque<int> cd;
int i, d, n, x, y, last;
inline void dfs(int poz){
    int lg[100001];
    bool sel[100001];
    memset(lg, 0, 100001);
    memset(sel, 0, 100001);
    cd.push_back(poz); sel[poz]=true; lg[poz]=1;
    while (!cd.empty()) {
        x=cd.front(); cd.pop_front();
        for (it=a[x].begin();it!=a[x].end();it++) if (!sel[*it]) {
            sel[*it]=true; lg[*it]=lg[x]+1; if (lg[*it]>d) d=lg[*it];
            cd.push_back(*it);
        }
    }
    last=x;
}
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);}
    dfs(1);
    dfs(last); printf("%d\n", d);
    return 0;
}