[백준/그래프] 1976번: 여행가자

 

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

1976번: 여행 가자

 

문제: 도시의 수와, 여행에 갈 도시의 수, 도시 간의 연결을 인접행렬로 받습니다. 이 정보들을 통해 계획한 도시들을 여행할 수 있는지 확인하는 문제입니다.

 

풀이: Union-find를 사용하여, 연결된 도시를 한 집합으로 묶습니다. 마지막에 여행할 도시들을 번호로 받는데 해당 번호들의 부모를 확인하고, 부모가 하나가 아니면 이 여행은 갈 수 없습니다.

 

 

import sys
input = sys.stdin.readline

N,M = int(input()), int(input())
parent = [i for i in range(N+2)]


#Root node 찾기
def find(x):
    if x== parent[x]:
        return x
    else:
        root_x = find(parent[x])
        parent[x] = root_x
        return parent[x]
 
def union(x,y):
    root_x = find(x)
    root_y = find(y)
 
    if root_x != root_y:
        parent[root_y] = root_x
    else:
        return

# 연결된 도시들을 한 집합으로 봅니다.
for i in range(1,N+1):
    link = list(map(int,input().split()))
    for j in range(1,len(link)+1):
        if link[j-1] == 1:
            union(i,j)

#여행계획을 확인합니다.
path = list(map(int,input().split()))
result = set([find(i) for i in path])
if len(result)!=1:
    print('NO')
else:
    print('YES')