Cod sursa(job #2320189)

Utilizator moltComan Calin molt Data 14 ianuarie 2019 14:47:00
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.2 kb
#include <bits/stdc++.h>
using namespace std;
ifstream in("darb.in");
ofstream out("darb.out");

vector<int> v[100005];
bool viz[100005],t[100005];
int n,nod1,nod2,ns,d[100005],capat1,capat2;

void DFS(int nod)
{
  viz[nod] = true;
  for (vector<int> :: iterator it = v[nod].begin();it != v[nod].end();++it)
       {int vecin = *it;
       if (viz[vecin] == false)
           {d[vecin] = d[nod] + 1;
           DFS(vecin);}
    }

}

int main()
{
    in>>n;
    for (int i = 1;i <= n - 1;++i)
    {
      in>>nod1>>nod2;
      t[nod2] = true;
      v[nod1].push_back(nod2);
      v[nod2].push_back(nod1);
    }
    for (int i = 1;i <= n;++i)
         {
            if (t[i] == false)
               {ns = i; break;}
         }
    d[ns] = 1;
    DFS(ns);
    int mx = -1;
    for (int i = 1;i <= n;++i)
         if (d[i] > mx)
             {mx = d[i];
             ns = i;}
    capat1 = ns;
    for (int i = 1;i <= n;++i)
        viz[i] = d[i] = 0;
    d[ns] = 1;
    DFS(ns);
    mx = -1;
    for (int i = 1;i <= n;++i)
    {
       if (d[i] > mx) { mx = d[i]; ns = i; }
    }
    capat2 = ns;
    for (int i = 1;i <= n;++i)
        viz[i] = d[i] = 0;
    d[capat1] = 1;
    DFS(capat1);
    out<<d[capat2];
    return 0;
}