여행 가자

• 여행 계획의 순서는 사실 상관이 없다. 그냥 계획에 있는 도시들이 모두 연결되어있기만 하면 여행이 가능하고, 그렇지 않다면 불가능하다.
• 그러므로, 계획에 있는 모든 도시들이 그래프상에서 전부 연결되어있는지만 확인하면 된다. 이것은 아무 점에서나 DFS나 BFS로 탐색을 해도 되고, Disjoint Set을 이용해서 컴포넌트들을 찾은 뒤 모든 도시들이 같은 컴포넌트 안에 있는지 확인하면 된다. DFS의 경우에는 O(V+E), Disjoint Set의 경우에는 O(E*α(V))가 걸린다. 이 문제의 경우는 엣지 갯수의 제한이 없으므로 E=O(V^2)이라고 생각해야 하고, 길이 m의 경로에 포함된 도시들을 찾는데에 필요한 O(m)을 추가하면 O(m + n^2) 또는 O(m + n^2*α(n))의 시간복잡도가 된다. 실제로는 Disjoint Set을 이용해서 구현했을때 좀더 빨랐다.

"""Solution code for "BOJ 1976. 여행 가자".

- Problem link: https://www.acmicpc.net/problem/1976
- Solution link: http://www.teferi.net/ps/problems/boj/1976

Tags: [DisjointSet]
"""

from teflib import disjointset


def main():
    N = int(input())
    M = int(input())  # pylint: disable=unused-variable
    dsu = disjointset.DisjointSet(N)
    for i in range(N):
        cities = input().split()
        for j, is_connected in enumerate(cities):
            if is_connected == '1':
                dsu.union(i, j)
    targets = [int(x) for x in input().split()]
    first = dsu.find(targets[0] - 1)
    is_all_reachable = all(dsu.find(target - 1) == first for target in targets)
    print('YES' if is_all_reachable else 'NO')


if __name__ == '__main__':
    main()

• Dependency: teflib.disjointset.DisjointSet