Cod sursa(job #2021353)

Utilizator raluca1234Tudor Raluca raluca1234 Data 13 septembrie 2017 12:50:39
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include <cstdio>
#include <vector>
#include <cstring>

#define maxN 100000

using namespace std;

vector <int> A[maxN+1];
int q[maxN+1], dist[maxN+1];

int maxD, maxNode;

void bfs(int node){
    maxD=0;
    int prim, ultim, nr;
    prim=ultim=1;
    q[prim]=node;
    dist[q[prim]]=1;
    while (prim<=ultim){
        nr=A[q[prim]].size();
        for (int i=0; i<nr; i++)
            if (!dist[A[q[prim]][i]]){
                q[++ultim]=A[q[prim]][i];
                dist[q[ultim]]=dist[q[prim]]+1;
                if (maxD<dist[q[ultim]]){
                    maxD=dist[q[ultim]];
                    maxNode=q[ultim];
                }
            }
        prim++;
    }
}

int main(){
    freopen("darb.in", "r", stdin);
    freopen("darb.out", "w", stdout);

    int N, x, y;
    scanf("%d", &N);
    for (int i=1; i<N; i++){
        scanf("%d%d", &x, &y);
        A[x].push_back(y);
        A[y].push_back(x);
    }
    bfs(1);
    memset(dist, 0, sizeof(dist));
    bfs(maxNode);
    printf("%d\n", maxD);

    return 0;
}