Cod sursa(job #1636842)

Utilizator Sanduleac_VladSanduleac Vllad Alexandru Sanduleac_Vlad 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;
}