Cod sursa(job #1592010)

Utilizator dianaorasanuDiana Orasanu dianaorasanu Data 6 februarie 2016 22:50:49
Problema Diametrul unui arbore Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <fstream>

#define NMAX 22000

using namespace std;

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

struct elem
{
    int nod;
    int d;
}C[NMAX], X;

void BFS(int x);

int n, m, M[NMAX][NMAX];
int incep, dist, i, x, y;
bool v[NMAX];

int main()
{
    fin >> n;
    for(i = 1; i < n; ++i)
    {
        fin >> x >> y;
        M[x][y] = M[y][x] = 1;
    }
    BFS(1);
    for(i = 1; i <= n; ++i)
        v[i] = false;
    BFS(incep);
    fout << dist << '\n';
    return 0;
}


void BFS(int x)
{
    int i;
    v[x] = true;
    int ic, sc;
    ic = sc = 1;
    C[ic].nod = x;
    C[ic].d = 1;
    while(ic <= sc)
    {
        X = C[ic];
        ic++;
        for(i = 1; i <= n; ++i)
            if(M[i][X.nod] == 1 && v[i] == false)
        {
            sc++;
            C[sc].nod = i;
            C[sc].d = X.d+1;
            v[i] = true;
        }
    }
    incep = C[sc].nod;
    dist = C[sc].d;
}