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