HackerEarth Rhezo and Critical Links problem solution YASH PAL, 31 July 202417 February 2026 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;} coding problems solutions HackerEarth HackerEarth