Cod sursa(job #1551700)

Utilizator ArkinyStoica Alex Arkiny Data 16 decembrie 2015 13:07:09
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include<fstream>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;

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

vector<int> A[100001];
queue<int> q;
int viz[100001];
int N,a,b,i,last_node,diametre=1;

void BFS(int n)
{
   q.push(n);
   viz[n]=1;
   int el;

   while(q.size())
   {
       el=q.front();
       last_node=el;
       q.pop();

       for(i=0;i<A[el].size();++i)
          if(!viz[A[el][i]])
          {
            q.push(A[el][i]);
            viz[A[el][i]]=1;
          }

   }
}

void DFS(int n,int father,int dim)
{
  diametre=max(dim,diametre);
  for(int i=0;i<A[n].size();++i)
  {
      if(A[n][i]!=father)
      {
          DFS(A[n][i],n,dim+1);
      }
  }
}

int main()
{
  in>>N;
  for(i=1;i<N;++i)
  {
     in>>a>>b;
     A[a].push_back(b);
     A[b].push_back(a);
  }

  BFS(1);
  diametre=1;
  DFS(last_node,0,1);
  out<<diametre;
}