Cod sursa(job #1579283)

Utilizator edim98Eduard Constantinescu edim98 Data 24 ianuarie 2016 16:38:11
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.87 kb
#include <bits/stdc++.h>
#define NMAX 100005

using namespace std;

FILE *fin = fopen("darb.in", "r");
FILE *fout = fopen("darb.out", "w");


void Search_start(int);
void Search_end(int);
void Add(int, int);
void Read();

int n, lst[2*NMAX], urm[2*NMAX], vf[2*NMAX], nr, dist[NMAX], dmax, start, _end;
bool viz[NMAX];
int Q[NMAX];


int main()
{
    Read();
    Search_start(1);
    Search_end(start);
}

void Add(int x, int y)
{
    nr++;
    vf[nr] = y;
    urm[nr] = lst[x];
    lst[x] = nr;
}

void Read()
{
    int x, y;

    fscanf(fin, "%d", &n);

    while(fscanf(fin, "%d%d", &x, &y) == 2)
    {
        Add(x, y);
        Add(y, x);
    }

    fclose(fin);
}

void Search_start(int nod)
{
    int poz, prim = 0, ultim = 1, x, y;

    Q[prim] = nod;
    dist[nod] = 1;
    viz[nod] = 1;

    while(prim <= ultim)
    {
        x = Q[prim++];
        poz = lst[x];
        while(poz != 0)
        {
            y = vf[poz];
            if(viz[y] == 0)
            {
                Q[ultim++] = y;
                dist[y] = dist[x] + 1;
                if(dist[y] >= dmax)
                    dmax = dist[y], start = y;
                viz[y]++;
            }
            poz = urm[poz];
        }
    }
}

void Search_end(int nod)
{

    int poz, prim = 0, ultim = 1, x, y;

    Q[prim] = nod;
    dist[nod] = 1;
    viz[nod] = 0;
    dmax = 0;

    while(prim <= ultim)
    {
        x = Q[prim++];
        poz = lst[x];
        while(poz != 0)
        {
            y = vf[poz];
            if(viz[y] == 1)
            {
                Q[ultim++] = y;
                dist[y] = dist[x] + 1;
                if(dist[y] >= dmax)
                    dmax = dist[y], _end = y;
                viz[y] = 0;
            }
            poz = urm[poz];
        }
    }

    fprintf(fout, "%d\n", dmax);
}