[이코테] CH10 그래프 이론 실전문제 41번 여행 계획

import sys
# sys.stdin.readline()
from collections import deque
sys.setrecursionlimit(100000000)
import heapq
import copy
import itertools
from itertools import combinations
from itertools import permutations
INF = 1e9
def find_parent(parent,x):
    if parent[x]!=x:
        parent[x] = find_parent(parent,parent[x])
    return parent[x]

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


N,M = map(int,sys.stdin.readline().split())
graph2 = []
for i in range(N):
    graph2.append(list(map(int,sys.stdin.readline().split())))
indegree = [0] * (N+1)
graph = [[] for _ in range(N+1)] 

parent = [0] *(N+1)
for i in range(N):
    parent[i] = i 

for i in range(N):
    for j in range(N):
        if graph2[i][j] == 1:
            indegree[j] += 1
            graph[i].append(j)
            union_parent(parent,i,j)
result = "YES"
path = list(map(int,sys.stdin.readline().split()))
arr = []
for i in range(len(path)-1):
    if find_parent(parent,path[i]) != find_parent(parent,path[i+1]):
        result = "NO"
print(result)

정신 차리자 !!!!! 

여행이 "가능한지" 라면

부모가 같은지 다른지를 보면 된다 (연결 되어있는지 유무만 확인하면 되니깐)

그래서 이건 그냥 신장트리가 같은 집합 안에 있는지 확인하면 되는 문제였다.....

그래서 ! 

비교해서 싸이클이 생기거나 부모가 다르면 ? 도달 불가

부모가 모두 같다면 같은 집합 안에 있는것이므로 도달이 가능하다.