[1717번] 집합의 표현 (유니온 파인드)

1717번: 집합의 표현

 

 유니온 파인드

여러 노드가 있을 때, 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union연산과 두 노드가 같은 집합에 속해 있는지를 확인하는 find연산으로 구성되어 있는 알고리즘

• union 연산 : 각 노드가 속한 집합을 1개로 합치는 연산
• find 연산 : 특정 노드 a에 관해 a가 속한 집합의 대표 노드를 반환하는 연산

 

원리

1. 1차원 리스트 이용, 각 노드가 모두 대표 노드이므로 리스트는 자신의 인덱스 값으로 초기화
2.  find연산
   1. 대상 노드 리스트에 index 값과 value값이 동일한지 확인
   2. 동일하지 않으면 value값이 가리키는 index 위치로 이동
   3. 이동 위치의 index값과 value값이 같을 때까지 반복 (재귀함수)
   4. 대표 노드에 도달하면 재귀 함수를 빠져나오면서 거치는 모든 노드값을 대표 노드 값으로 변경 ⭐️
3. union 연산 수행 : 2개의 노드를 선택해 각각의 대표 노드를 찾아 연결

 

경로 압축

그래프에서 여러 노드를 거쳐야 하는 경로에서 그래프를 변형해 더 짧은 경로로 갈 수 있도록 함으로써 시간 복잡도를 효과적으로 줄이는 방법

---

 

풀이

sys.setrecursionlimit(100000) : 재귀 최대 깊이 설정, 설정 안한 경우 시간 초과 떴음

"""
유니온 파인드

{0}, {1} ... {n} 각가 n+1개의 집합
합집합 연산과 두 원소가 같은 집합에 포함돼 있는지 확인

n (1~1,000,000), m : 입력으로 주어지는 연산의 개수

0 a b: a가 포함돼 있는 집함과 b가 포함돼 있는 집합 합침 -> union(a,b)
1 a b: 두 원소가 같은 집합에 포함돼 있는지 확인

7 8
0 1 3
1 1 7
0 7 6
1 7 1
0 3 7
0 4 2
0 1 1
1 1 1

"""

import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)
n, m = map(int, input().split())

#인덱스 배열
arr = [0] * (n+1)
for i in range(len(arr)):
    arr[i] = i


def find(a): # 대표노드 찾기
    if a == arr[a]:
        return a
    else:
        arr[a] = find(arr[a])
        return arr[a]

def union(a, b):
    a = find(a)
    b = find(b)
    if a != b:
        arr[b] = a


for i in range(m):
    q, a, b = map(int, input().split())
    if q == 0:  # 0 합침
        union(a, b)

    elif q == 1:  # 1 포함 확인
        if find(a) == find(b):
            print("YES")
        else:
            print("NO")

    print(arr)