HackerEarth Edges on a path problem solution

YASH PAL,
In this HackerEarth Edges on a path problem solution Given a connected graph with n nodes and m edges, where m <= n.You are also given two nodes a and b of the graph.
You need to find the number of edges which are present in all paths between a and b.
HackerEarth Edges on a path problem solution

HackerEarth Edges on a path problem solution.

#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <limits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <ratio>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#include <climits>
#define ll long long
#define ld long double
#define mp make_pair
#define pb push_back
#define in insert
#define vll vector<ll>
#define endl "n"
#define pll pair<ll,ll>
#define f first
#define s second
#define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++)
#define int ll
#define sz(x) (ll)x.size()
#define all(x) (x.begin(),x.end())
using namespace std;

 
const ll INF = 1e12;
const ll N =(1e5+5); // TODO : change value as per problem
const ll M = (3e5+5);
const ll MOD = 1e9+7;

vll graph[N];int U[M],V[M];//edge list representation of input graph
vll tree[N];//Bridge Tree formed from the given graph
bool isbridge[M]; // if i'th edge is a bridge edge or not 
int vis[N],arr[N],T,cmpno;//supporting stuff
queue<int> Q[N];
int nice[N];
int adj(int u,int e){
  return U[e]==u?V[e]:U[e];
}

int dfs0(int u,int edge)//mark bridges
{ 
  int dbe = arr[u] = T++;
  vis[u]=1;
  for(int i=0;i<graph[u].size();i++)
  {
    int e = graph[u][i];
    int w = adj(u,e);
    if(!vis[w])
      dbe = min(dbe,dfs0(w,e));
    else if(e!=edge)
      dbe = min(dbe,arr[w]);
  }
  if(dbe == arr[u] && edge!=-1)
    isbridge[edge]=true;
  return dbe;
}

void dfs1(int v)  //Builds the tree with each edge a bridge from original graph
{
  int currcmp = cmpno; // current component no.
  Q[currcmp].push(v);// A different queue for each component, coz during bfs we shall go to another component (step of dfs) and then come   back to this one and continue our bfs
  vis[v]=1;
  nice[v] = currcmp;
  while(!Q[currcmp].empty()) //bfs. Exploring all nodes of this  component
  {   
    int u = Q[currcmp].front();
    Q[currcmp].pop();    
    for(int i=0;i<graph[u].size();i++)
    {
      int e = graph[u][i];
      int w = adj(u,e);
      if(vis[w])continue;
      nice[w] = currcmp;
      if(isbridge[e])   //if the edge under consideration is bridge and other side is not yet explored, go there (step of dfs)
      {
        cmpno++;
        tree[currcmp].push_back(cmpno);
        tree[cmpno].push_back(currcmp);
        dfs1(w);
      }
      else  //else continue with our bfs
      {
        Q[currcmp].push(w);
        vis[w]=1;
      }
    }
  }
}
void solve(){
  int n,m;
  cin >> n >> m;
  int a,b;
  cin >> a >> b;
  a--;
  b--;
  for(int i= 0;i<m;i++){
    int u,v;
    cin >> u >> v;
    u--;
    v--;
    U[i] = v;
    V[i] = u;
    graph[u].pb(i);
    graph[v].pb(i);
  }
  dfs0(0,-1);
   memset(vis,0,sizeof(vis));
   dfs1(0);
   
   int u = nice[a];
   int v = nice[b];
   queue<int> q;
   vector<int> dis(cmpno+1,-1);
   dis[u] =0;
   q.push(u);
   while(!q.empty()){
    int p = q.front();
    q.pop();
    for(auto g:tree[p]){
      if(dis[g] == -1){
        dis[g] =  dis[p] + 1;
        q.push(g);
      }
    }
   }
   cout << dis[v] << endl;
}
signed main(){
 
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
     // freopen(".in","r",stdin);freopen(".out","w",stdout);
    
     ll tt=1;   
     // cin >> tt;
    while(tt--){    
        solve();
    }    
}

Second solution

#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;
template <class T, class L> inline bool smax(T &x, L y){  return x < y ? ( x = y, 1) : 0;  }
template <class T, class L> inline bool smin(T &x, L y){  return y < x ? ( x = y, 1) : 0;  }
typedef pair <int, int> pii;
typedef long long ll;

const int maxn = 1e5 + 17, lg = 17, mod = 1e9 + 7;
int n, m, q, edge[maxn], comp[maxn], h[maxn], gp, cnt[maxn], po[maxn], par[maxn][lg];
bool bl[maxn], seen[maxn], is[maxn];
vector<int> g[maxn];
pii e[maxn];
int hi(int v = 0, int p = -1){
    int ret = h[v];
    seen[v] = 1;
    for(auto i : g[v]){
    int u = edge[i] ^ v;
    if(!seen[u]){
        h[u] = h[v] + 1;
        int t = hi(u, v);
        if(t == h[u])  bl[i] = 1;
        smin(ret, t);
    }
    else if(u != p)  smin(ret, h[u]);
    }
    return ret;
}
void hello(int v){
    cnt[ comp[v] = gp ]++;
    for(auto i : g[v]){
    int u = edge[i] ^ v;
    if(!bl[i] && comp[u] == -1)
        hello(u);
    }
}
void dfs(int v = 0){
    for(int i = 1; i < lg; i++)  par[v][i] = par[ par[v][i - 1] ][i - 1];
    for(auto u : g[v])
    if(u != par[v][0]){
        h[u] = h[v] + 1, par[u][0] = v;
        cnt[u] += cnt[v];
        dfs(u);
    }
}
int lca(int v, int u){
    if(h[v] > h[u])  swap(v, u);
    for(int i = 0; i < lg; i++)
    if(h[u] - h[v] >> i & 1)
        u = par[u][i];
    for(int i = lg - 1; i >= 0; i--)
    if(par[v][i] != par[u][i])
        v = par[v][i], u = par[u][i];
    return v == u ? v : par[v][0];
}
void build_tree(){
    fill(g, g + n, vector<int>());
    for(int i = 0; i < m; i++)
    if(bl[i])
        g[ comp[ e[i].X ] ].push_back(comp[ e[i].Y ]),
        g[ comp[ e[i].Y ] ].push_back(comp[ e[i].X ]);
    dfs();
}
int main(){
    ios::sync_with_stdio(0), cin.tie(0);
    for(int i = po[0] = 1; i < maxn; i++)  po[i] = (po[i - 1] << 1) % mod;
    cin >> n >> m;
    int a, b;
    cin >> a >> b;
    a--, b--;
    for(int i = 0, v, u; i < m; i++){
    cin >> v >> u, v--, u--;
    edge[i] = v ^ u, e[i] = {v, u};
    g[v].push_back(i), g[u].push_back(i);
    }
    hi();
    memset(comp, -1, sizeof comp);
    for(int i = 0; i < n; i++)
    if(comp[i] == -1){
        hello(i);
        cnt[gp] = is[gp] = cnt[gp] - 1;
        gp++;
    }
    build_tree();
    cout << h[comp[a]] + h[comp[b]] - 2 * h[lca(comp[a], comp[b])] << 'n';
    return 0;
    cin >> q;
    for(int v, u; q--; ){
    cin >> v >> u, v--, u--;
    v = comp[v], u = comp[u];
    int p = lca(v, u);
    cout << po[ cnt[v] + cnt[u] - 2 * cnt[p] + is[p] ] << 'n';
    }
    return 0;
}
coding problems