# HackerEarth Furthest vertex problem solution

In this HackerEarth Furthest vertex problem solution There are n vertices.

Your task is to perform q queries:

1 a b - add an undirected edge of the length 1 between vertices a and b

2 a - find the distance to the furthest vertex reachable from the vertex a

Guaranteed that graph will not contain loops and cycles during all the time.

## HackerEarth Furthest vertex problem solution.

`#include <iostream>#include <cstdio>#include <cstdlib>#include <cstring>#include <string>#include <vector>#include <algorithm>#include <set>#include <map>#include <cmath>#include <ctime>#include <functional>#include <sstream>#include <fstream>#include <valarray>#include <complex>#include <queue>#include <cassert>#include <bitset>using namespace std;#ifdef LOCAL#define debug_flag 1#else#define debug_flag 0#endif  template <class T1, class T2 >std::ostream& operator << (std::ostream& os, const pair<T1, T2> &p) {  os << "[" << p.first << ", " << p.second << "]";  return os;}  template <class T >std::ostream& operator << (std::ostream& os, const std::vector<T>& v) {  os << "[";  bool first = true;  for (typename std::vector<T>::const_iterator it = v.begin(); it != v.end(); ++it)  {    if (!first)      os << ", ";    first = false;    os << *it;  }  os << "]";  return os;}#define dbg(args...) { if (debug_flag) { _print(_split(#args, ',').begin(), args); cerr << endl; } else { void(0);} }vector<string> _split(const string& s, char c) {  vector<string> v;  stringstream ss(s);  string x;  while (getline(ss, x, c))    v.emplace_back(x);  return v;}void _print(vector<string>::iterator) {}template<typename T, typename... Args>void _print(vector<string>::iterator it, T a, Args... args) {  string name = it -> substr((*it)[0] == ' ', it -> length());  if (isalpha(name[0]))    cerr << name  << " = " << a << " ";  else    cerr << name << " ";  _print(++it, args...);}typedef long long int int64;struct Query{  int type, a, b;  Query() : type(), a(), b() {}  Query(int _type, int _a, int _b) : type(_type), a(_a), b(_b) {}};const int N = (int)1e5 + 100;const int Q = (int)3e5 + 100;const int LOGN = 18;const int ADD_EDGE = 1;struct DSU{  int par[N];  DSU()  {    init();  }  void init()  {    for (int i = 0; i < N; i++)      par[i] = i;  }  int get_id(int a)  {    if (par[a] == a)      return a;    return par[a] = get_id(par[a]);  }  bool join(int a, int b)  {    a = get_id(a);    b = get_id(b);    if (a == b)      return false;    par[a] = b;    return true;  }};int n, q;vector<int> graph[N];Query q_list[Q];bool used[N];int h[N];int par[N][LOGN];int d1[N], d2[N];void dfs(int v, int p, int cur_h){  used[v] = true;  h[v] = cur_h;  par[v][0] = p;  for (int i = 1; i < LOGN; i++)  {    if (par[v][i - 1] == -1)      break;    par[v][i] = par[par[v][i - 1]][i - 1];  }  for (int to : graph[v])  {    if (to == p)      continue;    dfs(to, v, cur_h + 1);  }}int get_lca(int a, int b){  if (h[a] < h[b])    swap(a, b);  for (int i = LOGN - 1; i >= 0; i--)  {    int new_a = par[a][i];    if (new_a == -1 || h[new_a] < h[b])      continue;    a = new_a;  }  if (a == b)    return a;  for (int i = LOGN - 1; i >= 0; i--)  {    int new_a = par[a][i];    int new_b = par[b][i];    if (new_a == new_b)      continue;    a = new_a;    b = new_b;  }  return par[a][0];}int get_dist(int a, int b){  int l = get_lca(a, b);  return h[a] + h[b] - 2 * h[l];}void precalc(){  for (int i = 0; i < q; i++)  {    if (q_list[i].type != ADD_EDGE)      continue;    int a = q_list[i].a;    int b = q_list[i].b;    graph[a].push_back(b);    graph[b].push_back(a);  }  for (int i = 0; i < N; i++)    for (int j = 0; j < LOGN; j++)      par[i][j] = -1;  for (int i = 0; i < n; i++)  {    if (used[i])      continue;    dfs(i, -1, 0);  }  for (int i = 0; i < n; i++)    d1[i] = d2[i] = i;}int main(){#ifdef LOCAL  freopen ("input.txt", "r", stdin);#endif  scanf("%d%d", &n, &q);  for (int i = 0; i < q; i++)  {    int type;    scanf("%d", &type);    if (type == ADD_EDGE)    {      int a, b;      scanf("%d%d", &a, &b);      a--;      b--;      q_list[i] = Query(type, a, b);    }    else    {      int a;      scanf("%d", &a);      a--;      q_list[i] = Query(type, a, -1);    }  }  precalc();  DSU dsu = DSU();  for (int i = 0; i < q; i++)  {    if (q_list[i].type == ADD_EDGE)    {      int a = q_list[i].a;      int b = q_list[i].b;      int a_id = dsu.get_id(a);      int b_id = dsu.get_id(b);      int c1 = d1[a_id];      int c2 = d2[a_id];      int c3 = d1[b_id];      int c4 = d2[b_id];      assert(dsu.join(a, b));      int new_a = c2;      if (get_dist(c1, new_a) < get_dist(c1, c3))        new_a = c3;      if (get_dist(c1, new_a) < get_dist(c1, c4))        new_a = c4;      int new_b = c1;      if (get_dist(new_a, new_b) < get_dist(new_a, c2))        new_b = c2;      if (get_dist(new_a, new_b) < get_dist(new_a, c3))        new_b = c3;      if (get_dist(new_a, new_b) < get_dist(new_a, c4))        new_b = c4;      int id = dsu.get_id(a);      d1[id] = new_a;      d2[id] = new_b;    }    else    {      int a = q_list[i].a;      int a_id = dsu.get_id(a);      int dist1 = get_dist(a, d1[a_id]);      int dist2 = get_dist(a, d2[a_id]);      int ans = max(dist1, dist2);      printf("%d\n", ans);    }  }  return 0;}`