[Codeforces] E. We Need More Bosses

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : E. We Need More Bosses
Source            : Codeforces
Category          : Graph Theory
Algorithm         : Bridge Tree, Tree Diameter
Verdict           : Accepted

 
#include "bits/stdc++.h"
 
using namespace std;
 
#define FI              freopen("in.txt", "r", stdin)
#define FO              freopen("out.txt", "w", stdout)
#define FAST            ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
 
#define FOR(i, n)       for (int i = 1; i <= n; i++)
#define For(i, n)       for (int i = 0; i < n; i++)
#define ROF(i, n)       for (int i = n; i >= 1; i--)
#define Rof(i, n)       for (int i = n-1; i >= 0; i--)
#define FORI(i, n)      for (auto i : n)
#define eb              emplace_back
#define pb              push_back
#define ll              long long
#define ull             unsigned long long
#define vi              vector <int>
#define vl              vector <ll>
#define All(a)          a.begin(), a.end()
#define endl            '\n'
#define sz(a)           a.size()
#define lb              lower_bound
#define mod             1000000007
 
inline int setbit(int mask, int pos)      { return mask |= (1 << pos); }
inline int resetbit(int mask, int pos)    { return mask &= ~(1 << pos); }
inline int togglebit(int mask, int pos)   { return mask ^= (1 << pos); }
inline bool checkbit(int mask, int pos)   { return (bool)(mask & (1 << pos)); }
 
static const int maxn = 3e5 + 5;
static const int logn = 18;
 
struct node
{
      int v, e;
      node(int v = 0, int e = 0) : v(v), e(e) {}
};
 
vector <node> graph[maxn];
bool isBridge[maxn], vis[maxn];
int timer, dis[maxn], low[maxn];
 
inline void findBridge(int u = 1, int p = -1)
{
      vis[u] = 1;
      dis[u] = low[u] = ++timer;
      for (node it : graph[u])
      {
            int v = it.v;
            int e = it.e;
            if (v == p) continue;
            if (!vis[v])
            {
                  findBridge(v, u);
                  low[u] = min(low[u], low[v]);
                  if (dis[u] < low[v]) isBridge[e] = 1;
            }
            else
            {
                  low[u] = min(low[u], dis[v]);
            }
      }
}
 
int compo, compo_num[maxn];
bool used[maxn];
vector <int> tree[maxn];
 
inline void makeTree(int src)
{
      used[src] = 1;
      int cur_compo = compo;
      compo_num[src] = cur_compo;
      queue <int> PQ;
      PQ.emplace(src);
      while (!PQ.empty())
      {
            int u = PQ.front(); PQ.pop();
            for (node it : graph[u])
            {
                  int v = it.v;
                  int e = it.e;
                  if (used[v]) continue;
                  if (isBridge[e])
                  {
                        compo++;
                        tree[cur_compo].eb(compo);
                        tree[compo].eb(cur_compo);
                        makeTree(v);
                  }
                  else
                  {
                        PQ.emplace(v);
                        used[v] = 1;
                        compo_num[v] = cur_compo;
                  }
            }
      }
}
 
int maxDis, maxDisNode;
 
inline void dfs(int u, int p = -1, int level = 0)
{
      if (level > maxDis) maxDis = level, maxDisNode = u;
      for (int v : tree[u])
      {
            if (v == p) continue;
            dfs(v, u, level+1);
      }
}
 
int main()
{
      int tnode, tedge;
      cin >> tnode >> tedge;
      FOR(e, tedge)
      {
            int u, v;
            cin >> u >> v;
            graph[u].eb(v, e);
            graph[v].eb(u, e);
      }
      compo = 1;
      findBridge(1);
      makeTree(1);
      maxDis = -1, maxDisNode = -1;
      dfs(1);
      maxDis = -1;
      dfs(maxDisNode);
      cout << maxDis;
}