HackerEarth Delete and Cut Game problem solution YASH PAL, 31 July 2024 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';} coding problems