Cod sursa(job #2289526)

Utilizator ZappaManIosif Adrian-Mihai ZappaMan Data 24 noiembrie 2018 18:48:28
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.07 kb
#include <stdio.h>
#include <vector>
#include <stack>
#include <utility>

using namespace std;

const int NMAX = 100005;

int N;
vector<int> G[NMAX];


pair<int, int> dfs(int ix) {
   vector<bool> vis(N+1, false) ;
   vis[ix] = true;

   stack<pair<int,int>> st;
   st.push(make_pair(ix, 1));

   int ld = 0;
   int ln = -1;

   while (!st.empty()) {
      pair<int,int> top = st.top();
      st.pop();
      int n = top.first;
      int d = top.second;

      if (ld < d) {
         ld = d;
         ln = n;
      }

      for (int i : G[n]) {
         if (vis[i] == false) {
            vis[i] = true;
            int nd = d+1;
            st.push(make_pair(i, nd));
         }
      }
   }
   return make_pair(ln, ld);
}

int main() {
   freopen("darb.in", "r", stdin);
   freopen("darb.out", "w", stdout);

   scanf("%d", &N);

   for (int i = 1; i < N; ++i) {
      int x,y;
      scanf("%d %d", &x, &y);
      G[x].push_back(y);
      G[y].push_back(x);
   }

   int f = dfs(1).first;
   int d = dfs(f).second;

   printf("%d", d);


   fclose(stdin);
   fclose(stdout);
   return 0;
}