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


HackerEarth Delete and Cut Game problem solution.

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

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';
}