Cod sursa(job #2021355)

Utilizator AnaRaduAna-Maria Radu AnaRadu Data 13 septembrie 2017 12:58:02
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include <stdio.h>
#include <vector>
#include <queue>
#define nmax 100000

using namespace std;
std::vector <int> grf[nmax+1];
std::deque <int> dq;
int d[nmax+1];

void bfs(int nod){
    int i;
    d[nod]=1;
    dq.push_back(nod);
    while(!dq.empty()){
        for(i=0;i<grf[*dq.begin()].size();i++)
            if(d[grf[*dq.begin()][i]]==0){
                dq.push_back(grf[*dq.begin()][i]);
                d[grf[*dq.begin()][i]]=d[*dq.begin()]+1;
            }
        dq.pop_front();
    }
}

int main(){
    FILE *fin,*fout;
    fin=fopen("darb.in","r");
    fout=fopen("darb.out","w");
    int i,n,a,b,dmax=0,nodmax=0;
    fscanf(fin,"%d",&n);
    for(i=1;i<=n;i++){
        fscanf(fin,"%d%d",&a,&b);
        grf[a].push_back(b);
        grf[b].push_back(a);
    }
    bfs(1);
    for(i=1;i<=n;i++){
        if(d[i]>dmax){
            dmax=d[i];
            nodmax=i;
        }
        d[i]=0;
    }
    bfs(nodmax);
    for(i=1;i<=n;i++)
        if(d[i]>dmax)
            dmax=d[i];
    fprintf(fout,"%d",dmax);
    fclose(fin);
    fclose(fout);
    return 0;
}