Cod sursa(job #1908252)

Utilizator justsomedudePalade Thomas-Emanuel justsomedude Data 6 martie 2017 23:53:54
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.49 kb
#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
using namespace std;
/// http://www.infoarena.ro/problema/darb
ifstream fin  ("darb.in");
ofstream fout ("darb.out");

int N, M, nod, d[100002];
bool viz[100002];
vector <int> L[100002];

void BFS(int k)
{
  int j, i, maxim;
  queue <int> q;
  viz[k]=1;
  q.push(k);

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

    for (j=0; j<L[k].size(); j++)
    {
       i = L[k][j];
       if (!viz[i])
       {
          q.push(i);
          d[i] = d[k] + 1;
          viz[i]=1;
       }
    }
  }

  maxim=0; nod=0;
  for (i=1; i<=N; i++)
    if (d[i] > maxim)
    {
      maxim = d[i];
      nod = i;
    }
}

void BFS2(int k)
{
  int j, i, maxim;
  queue <int> q;
  for (i=1; i<=N; i++)
   viz[i]=0, d[i]=0;

  viz[k]=1;
  q.push(k);

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

    for (j=0; j<L[k].size(); j++)
    {
       i = L[k][j];
       if (!viz[i])
       {
          q.push(i);
          d[i] = d[k] + 1;
          viz[i]=1;
       }
    }
  }
  maxim=0;
  for (i=1; i<=N; i++)
    if (d[i] > maxim)
      maxim = d[i];
  fout << ++maxim << "\n";
}

int main ()
{
 int i, j, x, y;
 fin >> N;
 for (i=1; i<N; i++)
  {
     fin >> x >> y;
     L[x].push_back(y);
     L[y].push_back(x);
  }
 BFS(1);
 ///cout << nod << endl;
 /// extragem nod, rezultat al primei parcurgeri
 BFS2(nod);
 fin.close();
 fout.close();
 return 0;
}