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.

#include<bits/stdc++.h>
#define ll long long int
#define mod 1000000007
using 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;
}