ABC068 C - Cat Snuke and a Voyage

備忘録

問題

atcoder.jp

回答

import sys
import os
import math

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)]

MOD = 10 ** 9 + 7


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

    N, M = il()
    S = set()
    E = set()
    for m in range(M):
        a, b = il()
        if a == 1:
            S.add(b)
        if b == N:
            E.add(a)

    print('POSSIBLE' if len(S & E) == 1 else 'IMPOSSIBLE')


if __name__ == '__main__':
    main()

考え方

島1から島Nまで定期便を2つ使用して到達するためには、
島1 → どこかの島 → 島N と、経由する島を１つにしなければならない。

そのため、島１から到達することが出来る別の島と
島Nに到達することが出来る別の島の論理積を求めることで、
経由する必要がある島が１つか否かを判定することができる。