E - A Path in A Dictionary https://atcoder.jp/contests/abc417/tasks/abc417_e

abc417_e.py

import sys
from collections import deque

sys.setrecursionlimit(10**9)


def can_reach(v, current_visited):
    if v == Y:
        return True
    que = deque([v])
    tmp_visited = current_visited[:]
    tmp_visited[v] = True
    while que:
        u = que.popleft()
        for nxt in G[u]:
            if nxt == Y:
                return True
            if tmp_visited[nxt]:
                continue
            tmp_visited[nxt] = True
            que.append(nxt)
    return False


def dfs(v, path):
    if v == Y:
        return True
    for nxt in G[v]:
        if visited[nxt]:
            continue
        if not can_reach(nxt, visited): # nxtからYまで到達可能か判断
            continue
        visited[nxt] = True
        path.append(nxt)
        if dfs(nxt, path):
            return True
        path.pop()
        visited[nxt] = False
    return False


T = int(input())
ans = []
for _ in range(T):
    N, M, X, Y = map(int, input().split())
    G = [[] for _ in range(N + 1)]
    for _ in range(M):
        u, v = map(int, input().split())
        G[u].append(v)
        G[v].append(u)
    for i in range(1, N + 1):
        G[i].sort()
    visited = [False] * (N + 1)
    visited[X] = True
    path = [X]
    dfs(X, path)
    ans.append(path)

for a in ans:
    print(*a)