[백준] 1717. 집합의 표현 (+파이썬 코드)

Question. 백준 1717. 집합의 표현

 

 

 

---

Answer.

 

union-find 알고리즘을 구현하는 문제이다.

즉, union 함수랑 find_parent 함수를 구현할 수 있냐를 묻는 문제.

 

sol 1) 

union-find 알고리즘을 구현하고, 

같은 서로소 집합에 있는지 아닌지 확인해주는 함수를 구현해 풀었다.

 

import sys
sys.setrecursionlimit(1000000)  # maximum recursion depth exceed (한도 안 늘리면 runtime error 발생)
input = sys.stdin.readline

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

def union(parent, a, b):
    pa = find_parent(parent, a)
    pb = find_parent(parent, b)
    if pa < pb:
        parent[pb] = pa
    else:
        parent[pa] = pb

def same_disjoint_set(parent, a, b):
    if find_parent(parent, a) == find_parent(parent, b):
        return "YES"
    else:
        return "NO"

if __name__ == "__main__":
    n, m = map(int, input().split())
    parent = [i for i in range(n+1)]

    for _ in range(m):
        sig, a, b = map(int, input().split())
        if sig:
            print(same_disjoint_set(parent, a, b))
        else:
            union(parent, a, b)

 

 

sol 1)
Time Complexity	O(m*α(N))
Space Complexity	O(N)

 

 

 

-참고문헌

python maximum recursion depth exceed

Python3 최대 재귀한도 깊이 설정 ( Maximum recursion depth exceed )

백준 1717번: 집합의 표현 - runtime error 발생 해결

백준 1717번: 집합의 표현