백준 1717번 집합의 표현 | python | union-find

Konseo·2023년 10월 17일
0

코테풀이

목록 보기
54/59

문제

링크

풀이

  • union 함수와 find 함수만 알면 풀 수 있는 문제
  • union 함수 내 변수 주의
import sys
sys.setrecursionlimit(1000000) # 재귀 깊이 제한 늘리기
input = sys.stdin.readline

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

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

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

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

for _ in range(m):
    type,a,b=map(int,input().split())
    if type==0:
        union_parent(a,b)
    else:
        if find_parent(a)==find_parent(b):
            print('YES')
        else:
            print('NO')


profile
둔한 붓이 총명함을 이긴다

0개의 댓글