Mad City (Codeforces 1873H)
Tags: Others, games

Marcel and Valeriu are in the mad city, which is represented by $$$n$$$ buildings with $$$n$$$ two-way roads between them. Marcel and Valeriu start at buildings $$$a$$$ and $$$b$$$ respectively. Marcel wants to catch Valeriu, in other words, be in the same building as him or meet on the same road. During each move, they choose to go to an adjacent building of their current one or stay in the same building. Because Valeriu knows Marcel so well, Valeriu can predict where Marcel will go in the next move. Valeriu can use this information to make his move. They start and end the move at the same time.It is guaranteed that any pair of buildings is connected by some path and there is at most one road between any pair of buildings.Assuming both players play optimally, answer if Valeriu has a strategy to indefinitely escape Marcel.

Input: The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of test cases.The first line of each test case contains three space-separated integers $$$n$$$, $$$a$$$, $$$b$$$ ($$$3 \leq n \leq 2 \cdot 10^5$$$; $$$1 \leq a, b \leq n$$$) — the number of buildings (which equals the number of roads) and the starting buildings of Marcel and Valeriu.The following $$$n$$$ lines each contain two integers $$$u_i$$$, $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$u_i \neq v_i$$$) — there is a road between buildings $$$u_i$$$ and $$$v_i$$$. There is at most one road between any unordered pair of buildings.The sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.The roads are given that it is possible to get from any building to any other building going along the roads.

Output: For each test case output "YES" if Valeriu can escape Marcel forever and "NO" otherwise.You can output the answer in any case (for example, the strings "yEs", "yes", "Yes" and "YES" will be recognized as a positive answer).

Note: In the first test case the graph looks as follows:    Marcel starts at building $$$2$$$, while Valeriu starts at building $$$1$$$. Valeriu knows which way Marcel will move around the triangle, and he can simply always move in the same way to avoid Marcel forever.In the second test case the graph looks as follows:    Marcel starts at building $$$1$$$, while Valeriu starts at building $$$4$$$. Marcel can go to building $$$4$$$ on his first move and win, since Valeriu must either go to building $$$1$$$ (then he meets Marcel on the road from $$$1$$$ to $$$4$$$) or stay at building $$$4$$$ (then he meets Marcel at building $$$4$$$). So there is no strategy for Valeriu to win.

Sample Inputs:
6
3 2 1
2 1
3 2
1 3
4 1 4
1 4
1 2
1 3
2 3
4 1 2
1 2
2 3
2 4
3 4
7 1 1
4 1
2 1
5 3
4 6
4 2
7 5
3 4
8 5 3
8 3
5 1
2 6
6 8
1 2
4 8
5 7
6 7
10 6 1
1 2
4 3
5 8
7 8
10 4
1 9
2 4
8 1
6 2
3 1

Sample Outputs:
YES
NO
YES
NO
NO
YES

Solution (Python):
from collections import defaultdict

def dfs_to_find_cycle_entry(graph, start):
    visited = [False] * len(graph)
    parent = [-1] * len(graph)
    stack = [(start, -1)]
    while stack:
        (node, prev) = stack.pop()
        if visited[node]:
            return node
        visited[node] = True
        parent[node] = prev
        for neighbor in graph[node]:
            if not visited[neighbor] or neighbor != prev:
                stack.append((neighbor, node))
    return None

def bfs_to_find_distance(graph, start, target):
    visited = [False] * len(graph)
    distance = [0] * len(graph)
    queue = [start]
    visited[start] = True
    while queue:
        node = queue.pop(0)
        if node == target:
            return distance[node]
        for neighbor in graph[node]:
            if not visited[neighbor]:
                visited[neighbor] = True
                distance[neighbor] = distance[node] + 1
                queue.append(neighbor)
    return -1

def can_escape_using_cycle_distance(n, a, b, roads):
    graph = [[] for _ in range(n)]
    for (u, v) in roads:
        graph[u - 1].append(v - 1)
        graph[v - 1].append(u - 1)
    if a == b:
        return 'NO'
    cycle_entry = dfs_to_find_cycle_entry(graph, b - 1)
    valeriu_distance = bfs_to_find_distance(graph, b - 1, cycle_entry)
    marcel_distance = bfs_to_find_distance(graph, a - 1, cycle_entry)
    return 'YES' if valeriu_distance < marcel_distance else 'NO'
t = int(input().strip())
test_cases_user_input = []
for _ in range(t):
    (n, a, b) = map(int, input().strip().split())
    roads = [tuple(map(int, input().strip().split())) for _ in range(n)]
    test_cases_user_input.append((n, a, b, roads))
results_user_input = [can_escape_using_cycle_distance(n, a, b, roads) for (n, a, b, roads) in test_cases_user_input]
for result in results_user_input:
    print(result)

Solution (Python):
from sys import stdin
from collections import deque
t = int(stdin.readline().rstrip())

def bfs(s0):
    l = deque([s0])
    visited = set([s0])
    distance = [0 for _ in range(n)]
    while l:
        s = l.popleft()
        if s in cycle:
            return (distance[s], s)
        for v in g[s]:
            if v not in visited:
                l.append(v)
                distance[v] = distance[s] + 1
                visited.add(v)

def distance_cycle(u, v):
    d = 0
    while u != v:
        u = parents[u]
        d += 1
    if d <= len(cycle) // 2:
        return d
    else:
        return len(cycle) - d
for _ in range(t):
    (n, a, b) = map(int, stdin.readline().rstrip().split())
    (a, b) = (a - 1, b - 1)
    g = [[] for _ in range(n)]
    for _ in range(n):
        (u, v) = map(lambda x: int(x) - 1, stdin.readline().rstrip().split())
        g[u].append(v)
        g[v].append(u)
    if a == b:
        print('NO')
    else:
        cycle = set()
        parents = [-1 for _ in range(n)]
        visited = set()
        pile = [0]
        cycle_found = False
        while pile and (not cycle_found):
            s = pile.pop()
            if s not in visited:
                visited.add(s)
                for v in g[s]:
                    if v not in visited:
                        parents[v] = s
                        pile.append(v)
                    elif v != parents[s]:
                        parents[v] = s
                        cycle_found = True
                        break
        s0 = s
        cycle.add(s0)
        s = parents[s0]
        while s != s0:
            cycle.add(s)
            s = parents[s]
        (distance_a, cycle_a) = bfs(a)
        (distance_b, cycle_b) = bfs(b)
        dist = distance_cycle(cycle_a, cycle_b)
        if distance_a + dist <= distance_b:
            print('NO')
        else:
            print('YES')

Solution (Python):
from collections import deque
t = int(input())
for _ in range(t):
    (n, a, b) = map(int, input().split())
    adj = [[] for _ in range(n + 1)]
    for i in range(n):
        (u, v) = map(int, input().split())
        adj[u].append(v)
        adj[v].append(u)
    s = [b]
    visited = [False] * (n + 1)
    p = [0] * (n + 1)
    p[b] = b
    while s:
        v = s.pop()
        if visited[v]:
            end = v
            break
        visited[v] = True
        for u in adj[v]:
            if u != p[v]:
                p[u] = v
                s.append(u)
    q = deque([end])
    d = [-1] * (n + 1)
    d[end] = 0
    while q:
        v = q.popleft()
        for u in adj[v]:
            if d[u] == -1:
                d[u] = d[v] + 1
                q.append(u)
    if d[b] < d[a]:
        print('YES')
    else:
        print('NO')