1717 파이썬 집합의 표현

# 문제

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

1717번: 집합의 표현

 

유니온-파인드 알고리즘을 사용하는 기본 문제이다. 기본 문제라 굉장히 쉽다.

노드 수가 최대 100만개라 좀 걱정이 됐는데 유니온 파인드 알고리즘의 시간복잡도는 높이와 

관련이 있어서 그런지 해결이 됐다.

유니온은 합치는 것. 즉 노드들을 연결시키는 것

파인드는 루트 노드를 찾아 루트 노드가 같은지 확인을 해 두 노드가 같은 노드 집합에 

속해있는지 확인해주는 함수이다.

parent를 선언하고 자기 자신을 바라보도록 초기화를 해준다.

 

import sys
sys.setrecursionlimit(1000000)
n, m = map(int, (input().split()))
a = [list(map(int, sys.stdin.readline().split())) for _ in range(m)]

parent = []
for i in range(n+1):
    parent.append(i)

def find(x): #x의 루트 노드를 찾는 함수
    if x == parent[x]:
        return x

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


def union(x, y): # y를 x에 연결하는 함수
    xroot = find(x) # 각각 루트 노드를 찾아준다
    yroot = find(y)
    if xroot == yroot:
        return
    if xroot < yroot: # 루트 노드가 다르다면
        parent[yroot] = xroot
    else:
        parent[xroot] = yroot


for x, y, z in a:
    if x == 0: # 합집합
        union(y, z)

    else: # 포함되어있는지 확인
        yroot = find(y)
        zroot = find(z)
        if yroot == zroot:
            print("YES")
        else:
            print("NO")


#print(parent)