# HackerEarth Rhezo and Critical Links problem solution

In this HackerEarth Rhezo and Critical Links problem solution Rhezo likes to play with graphs having N nodes and M edges. Lonewolf is ready to give him such a graph only on one condition. He wants Rhezo to find the number of critical links in the graph.

A critical link in a graph is an edge that has the following property: If we cut the link/edge, the graph will have exactly one more connected component than it previously had, and the difference between the number of nodes on each side of the edge is less than a certain integer P.

Given P and the graph, can you help Rhezo calculate the number of critical links?

## HackerEarth Rhezo and Critical Links problem solution.

`#include<bits/stdc++.h>using namespace std;const int MAXN = 1e5+5;int disc[MAXN],low[MAXN];bool vis[MAXN];vector<int> adj[MAXN];int sz[MAXN];int CC[MAXN];int Number[MAXN];int tme=0,ans=0;int p,n;int cc=0;void DDFFSS(int s) {  vis[s]=true;  CC[s]=cc;  Number[cc]++;  for(int i=0;i<(int)adj[s].size();i++) if(!vis[adj[s][i]]) DDFFSS(adj[s][i]);}void DFS(int s, int par=-1) {  sz[s]=1;  ++tme;  low[s]=disc[s]=tme;  vis[s]=true;  for(int i=0;i<(int)adj[s].size();i++) {    int to=adj[s][i];    if(to==par) continue;    if(!vis[to]) {      DFS(to,s);      low[s]=min(low[s],low[to]);      sz[s]+=sz[to];      if(low[to]>disc[s] and abs(sz[to]-(Number[CC[s]]-sz[to]))<p) ans++;    }    else low[s]=min(low[s],disc[to]);  }}int main() {  // freopen("TASK.in","r",stdin);  // freopen("TASK.out","w",stdout);  int m;  cin>>n>>m>>p;  for(int i=1;i<=m;i++) {    int x,y;    scanf("%d%d",&x,&y);    adj[x].push_back(y);    adj[y].push_back(x);  }  for(int i=1;i<=n;i++) if(!vis[i]) ++cc,DDFFSS(i);  memset(vis,false,sizeof(vis));  for(int i=1;i<=n;i++) if(!vis[i]) DFS(i);  cout<<ans<<endl;  return 0;}`

### Second solution

`#include<bits/stdc++.h>using namespace std;vector<int> v[100100];int n, m, p, vis1[101000]={0}, disc[100100]={0}, low[100100]={0};int ans=0;int flag=0;int tim=0;int solve(int x, int prev, int nv){  vis1[x]=1;  disc[x]=low[x]=++tim;  int child=1;    for(int i=0; i<v[x].size(); i++){    if(v[x][i] != prev){      if(!vis1[v[x][i]]){        int sub_size=solve(v[x][i], x, nv);        child+=sub_size;        low[x]=min(low[x], low[v[x][i]]);        if(low[v[x][i]] > disc[x] && abs(nv-2*sub_size) < p){           ans++;          }      }      else        low[x]=min(low[x], disc[v[x][i]]);    }  }  return child;   }int main(){  cin>>n>>m>>p;  for(int i=0; i<m; i++){    int x, y;    cin>>x>>y;    v[x].push_back(y);        v[y].push_back(x);  }  int vis[100100]={0};  for(int i=1; i<=n; i++){    if(!vis[i]){      queue<int>q;      q.push(i);      int cnt=1;      vis[i]=1;      while(q.size()){        int top=q.front();        q.pop();          for(int i=0; i<v[top].size(); i++)          if(!vis[v[top][i]]){            cnt++;            vis[v[top][i]]=1;            q.push(v[top][i]);          }      }      solve(i,-1,cnt);    }  }  cout<<ans<<endl;  return 0;}`