Mai intai trebuie sa te autentifici.
Cod sursa(job #1636842)
Utilizator | Data | 7 martie 2016 12:52:56 | |
---|---|---|---|
Problema | Diametrul unui arbore | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.88 kb |
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
#define NMAX 100001
int N;
vector<int> con[NMAX];
int p[NMAX], ad[NMAX];
int lmax, pmax;
int dfs(int nod) {
int i, j;
if(ad[nod] > lmax) {
lmax = ad[nod];
pmax = nod;
}
for(i = 0; i < con[nod].size(); i++) {
if(con[nod][i] != p[nod]) {
int u = con[nod][i];
ad[u] = ad[nod] + 1;
p[u] = nod;
dfs(u);
}
}
}
int main() {
int i, j;
freopen("darb.in", "r", stdin);
freopen("darb.out", "w", stdout);
scanf("%d", &N);
for(i = 0; i < N; i++) {
int a, b;
scanf("%d %d", &a, &b);
con[a].push_back(b);
con[b].push_back(a);
}
dfs(1);
memset(ad, 0, sizeof(ad));
memset(p, 0, sizeof(p));
lmax = -1;
dfs(pmax);
printf("%d\n", lmax + 1);
return 0;
}