[파이썬] [그래프] 백준 1717 집합의 표현

문제

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

1717번: 집합의 표현

코드

import sys
sys.setrecursionlimit(1000000)
input=sys.stdin.readline

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

def union(b,c):
    b=find(b)
    c=find(c)

    if b<c:
        parent[c]=b
    else:
        parent[b]=c


n,m=map(int, input().split())

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

for i in range(m):
    a,b,c=map(int, input().split())
    if a==0:
        union(b,c)
    if a==1:
        if find(b)==find(c):
            print("YES")
        else:
            print("NO")

생각 정리

기본적인 union-find 문제이다