Skip to content
Programmingoneonone
Programmingoneonone
  • Home
  • CS Subjects
    • Internet of Things (IoT)
    • Digital Communication
    • Human Values
  • Programming Tutorials
    • C Programming
    • Data structures and Algorithms
    • 100+ Java Programs
    • 100+ C Programs
  • HackerRank Solutions
    • HackerRank Algorithms Solutions
    • HackerRank C problems solutions
    • HackerRank C++ problems solutions
    • HackerRank Java problems solutions
    • HackerRank Python problems solutions
Programmingoneonone

HackerEarth Rhezo and Destructive Mind problem solution

YASH PAL, 31 July 2024
In this HackerEarth Rhezo and Destructive Mind problem solution Rhezo has bought a graph with N nodes and M edges. He has a destructive mind and often deletes some nodes(and of course its edges to other nodes of the graph).
He will ask you Q queries. Each query is denoted by an integer X, meaning that he will delete the node X. Since he has a destructive mind, he gets satisfied if the the new graph with deleted node has more number of connected components than the original graph.
If satisfied, he wants you to print “Satisfied”(without quotes) and the number of edges that were removed when deleting node X, else print “Not Satisfied”(without quotes). All queries are different, and the original graph is restored after each query.
HackerEarth Rhezo and Destructive Mind problem solution

HackerEarth Rhezo and Destructive Mind problem solution.

#include<bits/stdc++.h>
using namespace std;
set<int> art;
const int MAXN = 1e2+5;
vector< int > adj[MAXN];
int low[MAXN],disc[MAXN];
int tme=0;
bool vis[MAXN];
void DFS(int s, int par=-1) {
vis[s]=true;
++tme;
int child=0;
low[s]=disc[s]=tme;
for(int i=0;i<(int)adj[s].size();i++) {
int to=adj[s][i];
if(to==par) continue;
if(!vis[to]) {
++child;
DFS(to,s);
low[s]=min(low[s],low[to]);
if(par==-1 and child>1) art.insert(s);
if(par!=-1 and low[to]>=disc[s]) art.insert(s);
}
else low[s]=min(low[s],disc[to]);
}
}
int main() {
// freopen("TASK.in","r",stdin);
// freopen("TASK.out","w",stdout);
int n,m;
cin>>n>>m;
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]) DFS(i);
int q;
cin>>q;
while(q--) {
int x;
scanf("%d",&x);
if(art.find(x)!=art.end()) printf("Satisfied %dn",(int)adj[x].size());
else printf("Not Satisfiedn");
}
return 0;
}

Second solution

#include<bits/stdc++.h>
#define siz 105
using namespace std;
vector<int>v[siz];
bool vis[siz],art[siz];
int n,num[siz],parent[siz],low[siz];
stack<int>st;
void dfs(int u)
{
static int time=1;
int children=0;
vis[u]=1;
num[u]=low[u]=time++;
for(int i=0;i<v[u].size();i++)
{
int curr=v[u][i];
if(!vis[curr])
{
children++;
parent[curr]=u;
dfs(curr);
low[u]=min(low[u],low[curr]);
if((!parent[u] && children>1) || (parent[u] && low[curr]>=num[u]))art[u]=1;
}
else if(curr!=parent[u])
low[u]=min(low[u],num[curr]);
}
}
int main()
{
int n,m,q;
scanf("%d%d",&n,&m);
int i;
for(i=0;i<m;i++)
{
int a,b;
scanf("%d%d",&a,&b);
v[a].push_back(b);
v[b].push_back(a);
}
for(i=1;i<=n;i++)
if(!vis[i])
dfs(i);
scanf("%d",&q);
while(q--)
{
int x;
scanf("%d",&x);
if(art[x])printf("Satisfied %dn",(int)v[x].size());
else printf("Not Satisfiedn");
}
return 0;
}
coding problems solutions

Post navigation

Previous post
Next post

Pages

  • About US
  • Contact US
  • Privacy Policy

Programing Practice

  • C Programs
  • java Programs

HackerRank Solutions

  • C
  • C++
  • Java
  • Python
  • Algorithm

Other

  • Leetcode Solutions
  • Interview Preparation

Programming Tutorials

  • DSA
  • C

CS Subjects

  • Digital Communication
  • Human Values
  • Internet Of Things
  • YouTube
  • LinkedIn
  • Facebook
  • Pinterest
  • Instagram
©2025 Programmingoneonone | WordPress Theme by SuperbThemes