Cod sursa(job #1408903)

Utilizator adi_ispas95FMI - Adrian Ispas adi_ispas95 Data 30 martie 2015 12:19:56
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.43 kb
#include <vector>
#include <queue>
#include <fstream>

using namespace std;

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

int vizitat[100001], vizitat2[100001], distanta[100001];
int n, m, i, j, x, y, nod, start, sfarsit, maxim;

int main()
{
    FILE *f = fopen("darb.in","r");
    FILE *g = fopen("darb.out","w");

    fscanf(f,"%d",&n);
    m = n - 1;

    for (i = 0; i < m; i++)
        {
            fscanf(f,"%d%d",&x,&y);
            v[x].push_back(y);
            v[y].push_back(x);
        }

    start = 1;
    vizitat[start] = 1;
    q.push(start);

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

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

    start = nod;
    vizitat2[start] = 1;
    q.push(start);

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

         for(i = 0; i < v[nod].size(); i++)
            if(!vizitat2[v[nod][i]])
                {
                    vizitat2[v[nod][i]] = 1;
                    distanta[v[nod][i]] = distanta[nod] + 1;
                    q.push(v[nod][i]);
                }
        }

    for(i = 1; i <= n; i++)
      if(maxim < distanta[i])
            maxim = distanta[i];

    fprintf(g,"%d",maxim + 1);

    return 0;
}