Mai intai trebuie sa te autentifici.
Cod sursa(job #1551076)
Utilizator | 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;
}