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

coding problems solutions