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


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;
}