Cod sursa(job #2196132)

Utilizator mihailrazMihail Turcan mihailraz Data 18 aprilie 2018 16:33:57
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include <fstream>
#include <vector>
#include <queue>
#define NMAX 100000

using namespace std;
ifstream fi("darb.in");
ofstream fo("darb.out");
int n, dmax, nod1, nod2;
int VIZ[NMAX+5];
vector <int> VEC[NMAX+5];
queue <int> Q;

void citire(void)
{
    int x, y;
    fi>>n;
    for(int i=1; i<=n-1; i++)
    {
        fi>>x>>y;
        VEC[x].push_back(y);
        VEC[y].push_back(x);
    }
}

void BFS(int src, int &extr)
{
    int nod, nods;
    Q.push(src);
    VIZ[src]=1;
    while(!Q.empty())
    {
        nod=Q.front();
        Q.pop();
        for(int i=0; i<VEC[nod].size(); i++)
        {
            nods=VEC[nod][i];
            if(!VIZ[nods])
            {
                VIZ[nods]=VIZ[nod]+1;
                Q.push(nods);
                if(VIZ[nods]>dmax)
                {
                    dmax=VIZ[nods];
                    extr=nods;
                }
            }
        }
    }
}

int main()
{
    citire();
    BFS(1, nod1);
    dmax=0;
    for(int i=1; i<=n; i++)
        VIZ[i]=0;
    BFS(nod1, nod2);
    fo<<dmax;
    fi.close();
    fo.close();
    return 0;
}