Cod sursa(job #1369466)

Utilizator PetrutiuPaulPetrutiu Paul Gabriel PetrutiuPaul Data 3 martie 2015 08:35:08
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

    ifstream fin("darb.in");
    ofstream fout("darb.out");

vector<int> v[100001];
queue<int> q;

int c[100001],viz[100001],last,dim;

void BFS( int nod )
{
    int i;

    q.push(nod);
    viz[nod]=1;
    c[nod]=1;

    while(!q.empty())
    {
        nod=q.front();

        for(i=0;i<v[nod].size();++i)
        {
            if(viz[v[nod][i]]==0)
            {
                q.push(v[nod][i]);
                c[v[nod][i]]=c[nod]+1;
                viz[v[nod][i]]=1;

                last=v[nod][i];
                dim=c[v[nod][i]];
            }
        }

        q.pop();
    }

}

int main()
{
    int m,i,x,y;

    fin>>m;

    for(i=1;i<m;i++)
    {
        fin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }

    BFS(1);

    for(i=1;i<=100000;i++)
        viz[i]=c[i]=0;

    BFS(last);

    fout<<dim;

}