[백준] 여행 가자

Look at the diagram on :https://my-coding-notes.tistory.com/332

If there is a valid path journey, it must exist in same disjoint set. So parent should be the same for the cities in that valid path because it is in same disjoint set.

Now I made a mistake in reading the input data. When link is coming in like [0, 1, 0] I should have been iterating through the element value, not the index. So not when j==1 we union, but when link[j]==1.

wrong:

n= int(input())
m = int(input())
parent = [i for i in range (n+1)]
for i in range(1,n+1):
    link = list(map(int, input().split()))
    for j in range(1,n+1):
        if j==1:
            union(parent, i,j)

correct:

def find_parent(parent, x):
    if parent[x]!=x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

def union(parent,a,b):
    a = find_parent(parent,a)
    b = find_parent(parent,b)
    if a<b:
        parent[b]=a
    else:
        parent[a]=b

n= int(input())
m = int(input())
parent = [i for i in range(n+1)]
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(parent, i,j)

path = list(map(int, input().split()))
check = set()
for city in path:
    check.add(find_parent(parent,city))
if len(check)==1:
    print("YES")
else:
    print("NO")