Cod sursa(job #1100590)

Utilizator ZoranZomboratZoran Zomborat Goran ZoranZomborat Data 7 februarie 2014 04:04:21
Problema Diametrul unui arbore Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include<fstream>
#include<vector>
#include<string.h>
#define N_max 100000
using namespace std;
struct
{
    int niv,nod;
}maxm;
vector <int> G[N_max];
int coada[N_max];
int nivel[N_max];
int viz[N_max];
int n,tata,fiu;

void BFS(int nod)
{
memset(viz,0,sizeof(viz));
maxm.niv=-1;
viz[nod]=1;
nivel[nod]=0;
    coada[0]=1;
    coada[1]=nod;
    for(int i=1;i<=coada[0];i++)
    {tata=coada[i];
        for(int j=0;j<G[tata].size();j++)
        {fiu=G[tata][j];
            if(!viz[fiu])
                {coada[++coada[0]]=fiu;
                 viz[fiu]=1;
                 nivel[fiu]=nivel[tata]+1;
                 if(nivel[fiu]>maxm.niv)
                 {
                     maxm.niv=nivel[fiu];
                     maxm.nod=fiu;
                 }
                }
        }
    }
}

int main()
{int x,y;
    ifstream fin("darb.in");
    ofstream fout("darb.out");
    fin>>n;
    for(int i=1;i<n;i++)
    {
        fin>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
    }

BFS(1);
BFS(maxm.nod);
fout<<maxm.niv+1;
}