1976_여행가자

https://www.acmicpc.net/problem/1976

1976번: 여행 가자

 

문제에서 중요한건 굳이 bfs나 dfs를 사용하여 탐색을 할 필요가 없다는 것이다.

 

여행계획에 속한다는 말은 결국 한 그래프 안에 여행경로에 들어있는 점들이 들어있는지 찾아보면 되는 것이기에 union과 find 연산을 통해서 부모를 등록시켜주고, 여행계획하는 점들의 부모를 찾아내면 쉽게 풀 수 있다.

 

import sys
input = sys.stdin.readline
n=int(input())
m=int(input())

def find(a):
    if parents[a] == a:
        return a
    parents[a] = find(parents[a])
    return parents[a]

def union(a,b):
    a,b = find(a),find(b)
    if a<b:
        parents[b] = a
    else:
        parents[a] = b

parents = [ i for i in range(n+1)]
for i in range(1,n+1):
    lst = [0] + list(map(int,input().split()))
    for j in range(i,n+1):
        if lst[j]==1:
            union(i,j)

plan = list(map(int,input().split()))
tmp = find(plan[0])
for i in plan:
    if find(i) != tmp:
        print('NO')
        break
else:
    print('YES')