[백준/Python] 1717번 집합의 표현 - (유니온파인드)

문제

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

 

소스코드

import sys 
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)

n, m =map(int, input().split())
parent = [i for i in range(n + 1)]
def union(a, b):
    a = find(a)
    b = find(b)
    if a < b:
        parent[b] = a
    if a > b:
        parent[a] = b

def find(a):
    if a == parent[a]:
        return a
    parent[a] = find(parent[a])
    return parent[a]

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

 

간단한 유니온파인드 문제입니다. 

union 함수부분을 랭킹기반이나 크기기반 등 최적화된 알고리즘을 사용하면 더욱 빨라집니다.