ABC168 D - .. (Double Dots)

備忘録

問題

atcoder.jp

回答

import sys

sys.setrecursionlimit(10000000)
import os
import math
import bisect
import collections
import itertools
import heapq
import re
import queue

# import fractions

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)
# lcm = lambda x, y: (x * y) // fractions.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, M = il()
    AB = {m + 1: [] for m in range(M+1)}
    for _ in range(M):
        a, b = il()
        AB[a].append(b)
        AB[b].append(a)

    visit = [0] * (N + 1)
    fifoqu = queue.Queue()
    fifoqu.put(1)

    while not fifoqu.empty():
        now = fifoqu.get()
        next = AB[now]
        for n in next:
            if visit[n] != 0:
                continue
            visit[n] = visit[now] + 1
            fifoqu.put(n)
    else:
        if visit[1] == 0:
            print('No')
            exit()
        else:
            visit[1] = 0
            print('Yes')
            for n in range(2, N + 1):
                deep = visit[n]
                rooms = AB[n]
                for room in rooms:
                    if visit[room] == deep - 1:
                        print(room)
                        break


if __name__ == '__main__':
    main()

考え方

部屋1を起点にして、幅優先探索を行う。
部屋1から1回の移動で到達できる全ての部屋に1,2回の移動で到達できる全ての部屋に2, ...
と、全ての部屋に対して1からの距離を求めておく。

その後、全ての部屋に対して、部屋1から自身の部屋に到達するまでに必要な移動数より、
一つ小さい部屋を探し、その部屋を次の部屋への道しるべとする。
例えば、部屋1から部屋Aに到達するまでに必要な移動回数がN回のとき、
部屋Aから1回の移動で到達できる部屋の中から、
部屋1からN-1回の移動で到達することが出来る部屋Bが部屋Aにとっての最短ルートとなる。