Cod sursa(job #1184648)

Utilizator AndreiOprisanFMI - Oprisan Andrei Daniel AndreiOprisan Data 13 mai 2014 18:49:24
Problema Diametrul unui arbore Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include<iostream>
#include<vector>
#include<queue>
#include<stdio.h>
#include<string.h>
#define MAX 100000
using namespace std;

vector<int> arb[MAX];
queue<int> coada;
int ultim,viz[MAX],lungime[MAX],diametru,el;

void darb(int prim)
{
    memset(viz,0,MAX);
    memset(lungime,0,MAX);
    viz[prim]=1;
    coada.push(prim);
    lungime[prim]=1;
    while(!coada.empty())
    {
        el=coada.front();
        coada.pop();
        for(int i=0;i<arb[el].size();i++)
            if(viz[arb[el][i]]==0)
        {
            viz[arb[el][i]]=1;
            coada.push(arb[el][i]);
            lungime[arb[el][i]]=lungime[el]+1;
            ultim=arb[el][i];
            diametru=lungime[arb[el][i]];
        }
    }
}

int main()
{
    FILE *f,*g;
    f=fopen("darb.in","r");
    g=fopen("darb.out","w");
    int n,a,b;
    fscanf(f,"%d",&n);
    for(int i=1;i<n;i++)
    {
        fscanf(f,"%d%d",&a,&b);
        arb[a].push_back(b);
        arb[b].push_back(a);
    }
    fclose(f);
    darb(1);
    darb(ultim);
    fprintf(g,"%d",diametru);
    fclose(g);
    return 0;
}