In this HackerEarth Weak nodes problem solution You are given N nodes with the following information:

The nodes are connected by M bidirectional edges.
Each node has a value Vi associated with it.
A node is called a weak node if the connections between some other nodes are broken when that node is deleted and any alternate connections are not present.
Write a program to tell the number of subsets from all the possible subsets of weak nodes, which on getting their values multiplied gives a number which is divisible by all primes less than 25.

Since the answer can be large, print the answer Modulo 10^9 + 7.


HackerEarth Weak nodes problem solution


HackerEarth Weak nodes problem solution.

#include<bits/stdc++.h>
#define MOD 1000000007
using namespace std;
#define ll long long
ll n, m, vis[500100];
vector<ll> v[500100];
ll disc[500100], low[500100], power[500100], tim=0;
vector<ll> ap;
ll isap[500100]={0};
void solve(ll x, ll prev){
vis[x]=1;
disc[x]=low[x]=++tim;
int child=0;
for(int i=0; i<v[x].size(); i++){
if(v[x][i] != prev){
if(!vis[v[x][i]]){
child++;
solve(v[x][i], x);
low[x] = min(low[x], low[v[x][i]]);
if(prev == -1 && child > 1 && !isap[x]){
isap[x]=1;
ap.push_back(x);
}
else if(prev != -1 && low[v[x][i]] >= disc[x] && !isap[x]){
isap[x]=1;
ap.push_back(x);
}
}
else
low[x] = min(low[x], disc[v[x][i]]);
}
}
}

ll POWER(ll a, ll b, ll mod)
{
ll ret = 1 ;
while(b)
{
if(b & 1 ) ret = ret*a % mod;
a = a*a % mod;
b >>= 1 ;
}
return ret;
}

int main(){
cin>>n>>m;
ll i, j, k;
for(i=1; i<=n; i++)
cin>>power[i];
for(i=0; i<m; i++){
ll x,y;
cin>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
for(i=1; i<=n; i++){
if(!vis[i])
solve(i,-1);
}
ll arr[9]={2, 3, 5, 7, 11, 13, 17, 19, 23};
ll f[600]={0};
for(i=0; i<ap.size(); i++){
ll temp=0;
for(j=0; j<9; j++)
if(power[ap[i]]%arr[j] == 0)
temp|=(1<<j);
f[temp]++;
}
for(i=0; i<512; i++){
f[i] = (POWER(2, f[i], MOD)-1+MOD)%MOD;
}
ll dp[2][10000]={0};
ll c=1, p=0;
for(i=0; i<512; i++){
ll temp=f[i];
for(j=0; j<512; j++)
dp[c][j] = dp[p][j];
for(j=0; j<512; j++){
dp[c][j|i] = (dp[c][j|i] + ((dp[p][j]*temp)%MOD))%MOD;
}
dp[c][i] = (dp[c][i] + temp)%MOD;
c=!c;p=!p;
}
cout<<dp[p][511]<<endl;
return 0;
}

Second solution

#include<bits/stdc++.h>
#define ll long long int
#define MOD 1000000007
using namespace std;

const int mx = 50005;
ll value[mx];
vector<int>adjacent[mx];
vector<int>weak;
bool visited[mx];
int disc[mx];
int low[mx];
int parent[mx];
int tim;

int prime[9] = {2,3,5,7,11,13,17,19,23};
bool ap[mx];

ll POWER(ll a, ll b, ll mod)
{
ll ret = 1 ;
while(b)
{
if(b & 1 ) ret = ret*a % mod;
a = a*a % mod;
b >>= 1 ;
}
return ret;
}

void dfs(int u)
{
visited[u] = true;

disc[u] = low[u] = ++tim;
int child = 0;
for(int i = 0 ; i < adjacent[u].size() ; i++){
int v = adjacent[u][i];

if(!visited[v])
{
child++;
parent[v] = u;
dfs(v);

low[u] = min(low[u], low[v]);

if(parent[u] != 0 && low[v] >= disc[u]) ap[u] = true;

if(parent[u] == 0 && child > 1) ap[u] = true;
}
else if(v != parent[u])
{
low[u] = min(low[u],disc[v]);
}
}
}

int main()
{
int N , M;
cin >> N >> M;

assert(1 <= N <= 50000 && 1 <= M <= 50000);

for(int i = 1 ; i <= N ; i++)
{
cin>>value[i];
assert( 1 <= value[i] <= 1000000000);
}

for(int i = 1 ; i <= M ; i++)
{
int u, v;
cin >> u >> v;

assert(1 <= u <= N);
assert(1 <= v <= N);

adjacent[u].push_back(v);
adjacent[v].push_back(u);
}

for(int i = 1 ; i <= N ; i++)
{
if(!visited[i]) dfs(i);
}

for(int i = 1 ; i <= N ; i++)
{
if(ap[i] == true) weak.push_back(i);
}

int size = weak.size();

vector<int>elem;
ll f[512] = {0};

for(int i = 0 ; i < size ; i++)
{
ll val = value[weak[i]];
ll ans = 0;
for(int j = 0 ; j < 9 ; j++)
{
int cnt = 0;
while(val % prime[j] == 0)
{
cnt++;
val /= prime[j];
}

if(cnt > 0)
{
ans |= (1 << j);
}
}

f[ans]++;
elem.push_back(ans);
}

for(int i=0; i<512; i++){
f[i] = (POWER(2, f[i], MOD)-1+MOD)%MOD;
}

ll dp[2][10000]={0};
ll c=1, p=0;

for(int i=0; i<512; i++){
ll temp=f[i];
for(int j=0; j<512; j++)
dp[c][j] = dp[p][j];
for(int j=0; j<512; j++){
dp[c][j|i] = (dp[c][j|i] + ((dp[p][j]*temp)%MOD))%MOD;
}
dp[c][i] = (dp[c][i] + temp)%MOD;
c=!c;p=!p;
}

cout<<dp[p][511]<<endl;
return 0;

}