[백준 1717번] 집합의 표현 - python / union-find 알고리즘

문제 링크

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

1717번: 집합의 표현

 

풀이 

Union-Find 알고리즘 

: 어떤 두 원소가 주어졌을 때 같은 집합에 속하는지 판별하는 알고리즘 

: 서로소 집합, 상호 배타적 집합 (Disjoint-set)

: union 함수 - 두 집합 합치기 

: find 함수 - 두 집합의 부모 구하기 

# Union-Find 알고리즘 
import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline 

def find(a):
    if a == parent[a]:
        return a
    # 루트 노드 찾기 
    p = find(parent[a])
    # 루트 노드 갱신 
    parent[a] = p 
    return parent[a]
    
def union(a,b):
    # 루트 노드 찾기 
    a = find(a)
    b = find(b)
    
    # 두 루트 노드가 같다면 동일한 집합 
    if a == b:
        return
    # 두 집합 합치기  
    if a < b :
        parent[b] = a
    else :
        parent[a] = b
        
n, m = map(int,input().split())

# 부모 테이블 
parent = [0] * (n+1)

# 자기 자신을 설정 
for i in range(1,n+1):
    parent[i] = i 
    
for _ in range(m):
    cal, a, b = map(int,input().split())
    
    # 합치기 
    if cal == 0:
        union(a,b)
    else:
        # 같은 집합인지 확인하기 
        if find(a) == find(b):
            print('YES')
        else:
            print("NO")

- 처음에 런타임 에러가 발생하였는데 sys.setrecursionlimit(100000) 추가해줌으로서 해결