Removing Graph (Codeforces 1823E)
Tags: Math, games

Alice and Bob are playing a game on a graph. They have an undirected graph without self-loops and multiple edges. All vertices of the graph have degree equal to $$$2$$$. The graph may consist of several components. Note that if such graph has $$$n$$$ vertices, it will have exactly $$$n$$$ edges.Alice and Bob take turn. Alice goes first. In each turn, the player can choose $$$k$$$ ($$$l \le k \le r$$$; $$$l < r$$$) vertices that form a connected subgraph and erase these vertices from the graph, including all incident edges.The player who can't make a step loses.For example, suppose they are playing on the given graph with given $$$l = 2$$$ and $$$r = 3$$$:  A valid vertex set for Alice to choose at the first move is one of the following:   $$$\{1, 2\}$$$  $$$\{1, 3\}$$$  $$$\{2, 3\}$$$  $$$\{4, 5\}$$$  $$$\{4, 6\}$$$  $$$\{5, 6\}$$$  $$$\{1, 2, 3\}$$$  $$$\{4, 5, 6\}$$$  Suppose, Alice chooses subgraph $$$\{4, 6\}$$$.Then a valid vertex set for Bob to choose at the first move is one of the following:   $$$\{1, 2\}$$$  $$$\{1, 3\}$$$  $$$\{2, 3\}$$$  $$$\{1, 2, 3\}$$$  Suppose, Bob chooses subgraph $$$\{1, 2, 3\}$$$.Alice can't make a move, so she loses.You are given a graph of size $$$n$$$ and integers $$$l$$$ and $$$r$$$. Who will win if both Alice and Bob play optimally.

Input: The first line contains three integers $$$n$$$, $$$l$$$ and $$$r$$$ ($$$3 \le n \le 2 \cdot 10^5$$$; $$$1 \le l < r \le n$$$) — the number of vertices in the graph, and the constraints on the number of vertices Alice or Bob can choose in one move.Next $$$n$$$ lines contains edges of the graph: one edge per line. The $$$i$$$-th line contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$; $$$u_i \neq v_i$$$) — description of the $$$i$$$-th edge.It's guaranteed that the degree of each vertex of the given graph is equal to $$$2$$$.

Output: Print Alice (case-insensitive) if Alice wins, or Bob otherwise.

Note: In the first test the same input as in legend is shown.In the second test the same graph as in legend is shown, but with $$$l = 1$$$ and $$$r = 2$$$.

Sample Inputs:
6 2 3
1 2
2 3
3 1
4 5
5 6
6 4

6 1 2
1 2
2 3
3 1
4 5
5 6
6 4

12 1 3
1 2
2 3
3 1
4 5
5 6
6 7
7 4
8 9
9 10
10 11
11 12
12 8

Sample Outputs:
Bob

Bob

Alice

Solution (Python):
""""""
import sys
import math
input = sys.stdin.readline

def inp():
    return int(input())

def inlt():
    return list(map(int, input().split()))

def insr():
    s = input()
    return list(s[:len(s) - 1])

def invr():
    return map(int, input().split())

def DFS(st):
    q = [(st, 0)]
    size = 0
    while q:
        (cur, pre) = q.pop()
        if vis[cur]:
            return size
        vis[cur] = 1
        size += 1
        for i in g[cur]:
            if i == pre:
                continue
            q.append((i, cur))
if __name__ == '__main__':
    (n, l, r) = invr()
    g = [[] for _ in range(n + 1)]
    for _ in range(n):
        (u, v) = invr()
        g[u].append(v)
        g[v].append(u)
    vis = [0] * (n + 1)
    ans = 0
    for i in range(1, n + 1):
        if vis[i] == 0:
            sz = DFS(i)
            nim = sz // l if sz < l + r else 0
            ans ^= nim
    print('Alice' if ans else 'Bob')

Solution (Python):
from sys import setrecursionlimit
import threading

def main():
    (n, l, r) = map(int, input().split())
    g = [[] for i in range(0, n)]
    for i in range(0, n):
        (a, b) = map(int, input().split())
        a -= 1
        b -= 1
        g[a].append(b)
        g[b].append(a)
    res = 0
    used = [False for i in range(0, n)]

    def dfs(v):
        used[v] = True
        size = 1
        for to in g[v]:
            if not used[to]:
                size += dfs(to)
        return size
    for i in range(0, n):
        if not used[i]:
            size = dfs(i)
            if size <= l + r - 1:
                res ^= size // l
    if res:
        print('Alice')
    else:
        print('Bob')
setrecursionlimit(10 ** 9)
threading.stack_size(2 ** 27)
thread = threading.Thread(target=main)
thread.start()

Solution (Python):
from sys import setrecursionlimit
import threading

def main():
    (n, l, r) = map(int, input().split())
    g = [[] for i in range(0, n)]
    for i in range(0, n):
        (a, b) = map(int, input().split())
        a -= 1
        b -= 1
        g[a].append(b)
        g[b].append(a)
    res = 0
    used = [False for i in range(0, n)]

    def dfs(v):
        used[v] = True
        size = 1
        for to in g[v]:
            if not used[to]:
                size += dfs(to)
        return size
    for i in range(0, n):
        if not used[i]:
            size = dfs(i)
            if size <= l + r - 1:
                res ^= size // l
    if res:
        print('Alice')
    else:
        print('Bob')
setrecursionlimit(10 ** 9)
threading.stack_size(2 ** 27)
thread = threading.Thread(target=main)
thread.start()