Cod sursa(job #1197543)

Utilizator bogdanmarin69Bogdan Marin bogdanmarin69 Data 12 iunie 2014 16:10:20
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include <cstdio>
#include <queue>
#include <vector>
#include <cstring>

using namespace std;
#define MAX 100001
#define max(a,b) (((a>b))?(a):(b))
queue <int> q;
vector <int> gr[MAX];
int d[MAX], dmax, st, n;
void bfs(int nod);
int main()
{
    int i, x, y;
    freopen("darb.in", "r", stdin);
    freopen("darb.out", "w", stdout);
    scanf("%d", &n);
    for(i=1; i<=n; i++){
        scanf("%d%d", &x, &y);
        gr[x].push_back(y); gr[y].push_back(x);
    }
    bfs(1);
    bfs(st);
    printf("%d\n", dmax+1);
    return 0;
}
void bfs(int nod){
    unsigned int j;
    int x;
    memset(d, 0, (n+1)*sizeof(int));
    q.push(nod);
    while(!q.empty()){
        x = q.front(); q.pop();
        for(j=0; j<gr[x].size(); j++)
            if(d[gr[x][j]]==0){
                d[gr[x][j]] = 1 + d[x];
                q.push(gr[x][j]);
                if(dmax<d[gr[x][j]]){
                    dmax = d[gr[x][j]];
                    st = gr[x][j];
                }
            }
    }
}