BOJ - 1976 - 여행 가자

Updated:

import sys

def find(x):
    if(parent[x] == x): return x

    parent[x] = find(parent[x])
    return parent[x]

def unionx(x, y):
    rootX = find(x)
    rootY = find(y)

    if not rootX == rootY: parent[rootY] = rootX

N = int(input())
M =  int(input())

maps = []
parent = [i for i in range(N + 1)]
for _ in range(N):
    maps.append(list(map(int, sys.stdin.readline().split())))
tour = list(map(int, sys.stdin.readline().split()))

for i in range(N):
    for j in range(i, N):
        if maps[i][j] == 1:
            unionx(i + 1, j + 1)

result = set([find(i) for i in tour])

if len(result) == 1: print("YES")
else: print("NO")

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

Categories:

Updated:

Leave a comment