Cod sursa(job #2667742)

Utilizator sebastian.barbarasaSebastian Barbarasa sebastian.barbarasa Data 3 noiembrie 2020 19:49:15
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.22 kb
#include <fstream>
#include <vector>
#include <queue>
#define NMAX 100004
using namespace std;

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

vector <int>v[NMAX];
queue <int>q;
int d[NMAX];
int n, now, lg;
int maxx, vf;

int main()
{
 int i,x,y;
 fin>>n;
 for (i=1; i<n; i++)
     {
      fin>>x>>y;
      v[x].push_back(y);
      v[y].push_back(x);
     }
 q.push(1);
 d[1]=1;
 while (!q.empty())
       {
        now=q.front(); q.pop();
        lg=v[now].size();
        for (i=0; i<lg; i++)
             if (!d[v[now][i]])
                {
                d[v[now][i]]=d[now]+1;
                q.push(v[now][i]);
                }
       }
 for (i=1; i<=n; i++)
     {
      if (d[i]>maxx)
         {
          maxx=d[i];
          vf=i;
         }
      d[i]=0;
     }
 d[vf]=1; maxx=0;
 q.push(vf);
 while (!q.empty())
       {
        now=q.front(); q.pop();
        lg=v[now].size();
        for (i=0; i<lg; i++)
             if (!d[v[now][i]])
                {
                 maxx=max(maxx,d[now]+1);
                 d[v[now][i]]=d[now]+1;
                 q.push(v[now][i]);
                }
       }
 fout<<maxx<<'\n';
 fin.close();
 fout.close();
 return 0;
}