Cod sursa(job #2450059)

Utilizator corina_dimitriuDimitriu Corina corina_dimitriu Data 21 august 2019 18:26:17
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.11 kb
#include <fstream>
#include <vector>
#define DMAX 100005

using namespace std;
ifstream fin("darb.in");
ofstream fout("darb.out");
vector <int> A[DMAX];
bool uz[DMAX];
int n,maxim,vf,C[DMAX],dmax,D[DMAX],ultim;
void DFS(int varf, int dist);
void BFS();
int main()
{int i,a,b;
    fin>>n;
    for(i=1;i<n;i++)
       {fin>>a>>b;
        A[a].push_back(b);
        A[b].push_back(a);
       }
    DFS(1,0);
    BFS();
    fout<<D[C[ultim]];
    return 0;
}
void DFS(int varf, int dist)
{
   //for(auto it: A[varf])
   if(dist>maxim)
     {
       maxim=dist;
       vf=varf;
     }
   for(vector <int>::iterator it=A[varf].begin();it!=A[varf].end();it++)
       if(!uz[*it])
         {
          uz[*it]=1;
          DFS(*it,dist+1);
         }
}
void BFS()
{int prim,i,elem;
 for(i=1;i<=n;i++)
     uz[i]=0;
 C[1]=vf;
 D[vf]=1;
 uz[vf]=1;
 prim=ultim=1;
 while(prim<=ultim)
     {
       elem=C[prim++];
       for(auto it: A[elem])
           if(!uz[it])
             {
              uz[it]=1;
              D[it]=D[elem]+1;
              C[++ultim]=it;
             }
     }
}