# HackerEarth Weak nodes problem solution

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.

`#include<bits/stdc++.h>#define MOD 1000000007using namespace std;#define ll long longll 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 1000000007using 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;}`