# HackerEarth Delete and Cut Game problem solution

In this HackerEarth Delete and Cut Game problem solution, You are given a connected graph with N nodes and M edges. Two players A and B are playing a game with this graph. A person X chooses an edge uniformly, randomly, and removes it. If the size (number of nodes in component) of two non-empty connected component created are EVEN, then A wins otherwise player B wins.

Find the probability of winning the game for A and B. The probability is of the P/Q form where P and Q are both coprimes. Print PQ-1 module 1000000007.
Note: X can only select the edges which divide the graph into two non-empty connected components after they are removed. If no such edge is present in the graph, then the probability to win can be 0 for both A and B.

## HackerEarth Delete and Cut Game problem solution.

`#include<bits/stdc++.h>#define ll long long int#define mod 1000000007using namespace std;const int N = 100009;const int M = 100009;vector<int>E[N];vector<int>graph[N];int U[M], V[M];bool isbridge[M];int visited[N];int arr[N],T;int cmpno;queue<int> Q[N];int compo[N];int region[N];int sz;int dp[N];ll power(ll a, ll n){    if(n == 0) return 1;    ll ans = 1;    ll val = a;    while(n)    {        if(n%2)        {            ans *= val;            ans %= mod;        }        val *= val;        val %= mod;        n /= 2;    }    return ans;}int adj(int u, int e){    return U[e] == u ? V[e]:U[e];}int dfs0(int u, int edge){    visited[u] = 1;    arr[u] = T++;    int dbe = arr[u];    for(int i = 0 ; i < graph[u].size() ; i++)    {        int e = graph[u][i];        int w = adj(u,e);        if(!visited[w])        {            dbe = min(dbe,dfs0(w,e));        }        else if(e != edge)        {            dbe = min(dbe, arr[w]);        }    }    if(dbe == arr[u] && edge != -1)    {        isbridge[edge] = true;    }    return dbe;}void dfs2(int v){    int currcmp = cmpno;    sz = max(sz,currcmp+1);    Q[currcmp].push(v);    visited[v]=1;    while(!Q[currcmp].empty())    {        int u = Q[currcmp].front();        region[currcmp]++;        compo[u]=currcmp;        Q[currcmp].pop();        for(int i=0;i<(int)graph[u].size();i++)        {            int e = graph[u][i];            int w = adj(u,e);            if(visited[w])continue;            if(isbridge[e])            {                cmpno++;                E[cmpno].push_back(currcmp);                E[currcmp].push_back(cmpno);                dfs2(w);            }            else            {                Q[currcmp].push(w);                visited[w]=1;            }        }    }}int dfs1(int u){    visited[u] = true;    int flag = 0;    int sum = 0;    for(int i = 0 ; i < E[u].size() ; i++)    {        int v = E[u][i];        if(!visited[v])        {            flag = 1;            sum += dfs1(v);        }    }    if(!flag)    {        dp[u] = region[u];        return dp[u];    }        dp[u] = sum + region[u];    return dp[u];}int main(){    int n,m;    cin>>n>>m;    for(int i = 0 ; i < m ; i++)    {        int u,v;        cin>>u>>v;        u--;        v--;        U[i] = v;        V[i] = u;        graph[u].push_back(i);        graph[v].push_back(i);    }    dfs0(0,-1);    memset(visited,0,sizeof(visited));    dfs2(0);    memset(visited,0,sizeof(visited));    dfs1(0);    ll winA = 0;    ll winB = 0;    for(int i = 0 ; i < sz ; i++)    {        for(int j = 0 ; j < E[i].size() ; j++)        {            int v = E[i][j];            int f = min(dp[i],dp[v])%2;            int s = (n - min(dp[i],dp[v]))%2;            if(f == 0 && s == 0)            {                winA++;            }            else            {                winB++;            }        }    }       winA /= 2;    winB /= 2;    int temp = winA + winB;    winA *= power(temp,mod-2);    winA %= mod;    winB *= power(temp,mod-2);    winB %= mod;    cout<<winA<<" "<<winB<<endl;}`

### Second solution

`#include <bits/stdc++.h>using namespace std;typedef long long ll;const int maxn = 1e5 + 17, mod = 1e9 + 7;struct E{    int v, u;    bool bl;    int o(int x){        return x == v ? u : v;    }}  e[maxn];int n, m, sz[maxn], hi[maxn], h[maxn];vector<E*> g[maxn];bool mark[maxn];void dfs(int v = 0, int p = -1){    mark[v] = 1;    sz[v] = 1;    hi[v] = h[v];    for(auto e : g[v]){        int u = e -> o(v);        if(u != p)            if(!mark[u]){                h[u] = h[v] + 1;                dfs(u, v);                sz[v] += sz[u];                if(hi[u] == h[u])                    e -> bl = 1;                hi[v] = min(hi[v], hi[u]);            }            else                hi[v] = min(hi[v], h[u]);    }}int rev(int a){    int ans = 1;    for(int b = mod - 2; b; b >>= 1, a = (ll) a * a % mod)        if(b & 1)            ans = (ll) ans * a % mod;    return ans;}int main(){    ios::sync_with_stdio(0), cin.tie(0);    cin >> n >> m;    for(int i = 0; i < m; i++){        cin >> e[i].v >> e[i].u;        e[i].v--, e[i].u--;        g[e[i].v].push_back(&e[i]);        g[e[i].u].push_back(&e[i]);    }    dfs();    int a = 0, b = 0;    for(int i = 0; i < m; i++)        if(e[i].bl){            int cmp = min(sz[e[i].v], sz[e[i].u]);            if(n % 2 == 0 && cmp % 2 == 0)                a++;            else                b++;        }    cout << (ll) a * rev(a + b) % mod << ' ' << (ll) b * rev(a + b) % mod << '\n';}`