[자료구조] 서로소 집합

자료 출처: https://youtu.be/aOhhNFTIeFI

1. 서로소 집합 자료구조

공통 원소가 없는 두 집합으로, Union Find 자료구조라고도 한다.

• 합집합(Union): 두 개의 원소가 포함된 집합을 하나의 집합으로 합침
• 찾기(Find): 특정 원소가 속한 집합이 어느 집합인지 알려줌

2. 여러 개의 합치기 연산

• 합집합(Union) 연산을 확인하고 서로 연결된 두 노드 A, B를 확인한다.
  • A, B의 루트 노드인 A', B'를 각각 찾는다.
  • A'를 B'의 부모 노드로 설정한다.
• 모든 합집합 연산이 처리될 때까지 위의 과정을 반복한다.

3. 무방향 그래프 내에서 사이클을 판별하기 위한 용도

• (방향 그래프에서는 DFS를 이용)
• 각 간선을 하나씩 확인하며 두 노드의 루트 노드를 확인한다
  • 루트 노드가 서로 다른 경우, 두 노드에 대해 합집합 연산을 수행한다.
  • 루트 노드가 서로 같은 경우(즉 두 노드가 같은 집합에 포함된 경우), 사이클이 발생한 것이다.
• 그래프에 포함된 모든 간선에 대하여 위의 과정을 반복한다.

4. 파이썬 구현

# 특정 원소가 속한 집합 찾기
def find_parent(parent, x): # parent는 부모 테이블을 의미
    if parent[x] != x: # x의 부모 노드가 자기 자신이 아닌 경우
        # 부모 테이블(parent)과 부모 노드(parent[x])를 가지고 find_parent 함수를 다시 호출
        # 부모 노드가 자기 자신이 되는 경우를 찾아 올라감
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

# 두 원소가 속한 집합을 합치기
def union_parent(parent, a, b):
    a = find_parent(parent, a) # 부모 테이블에서 a의 부모 노드 찾기
    b = find_parent(parent, b) # 부모 테이블에서 b의 부모 노드 찾기
    
    # 작은 노드를 큰 노드의 부모로 설정해줌
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

# 노드 개수와 간선 개수를 입력 받기
v, e = map(int, input().split())

# 부모 테이블 초기화
parent = [0] * (v + 1)

for i in range(1, v + 1): # 모든 노드에 대하여
    parent[i] = i # 부모를 자기 자신으로 초기화

cycle = False # 사이클 발생 여부

for i in range(e): # 모든 간선에 대하여

    # 두 노드가 같은 집합에 속해있는 경우 사이클이 발생하여 종료
    if find_parent(parent_a) == find_parent(parent, b):
        cycle = True
        break
    
    # 사이클이 발생하지 않았다면 합집합 연산 수행
    else:
        uinon_parent(parent, a, b)
        
if cycle:
    print("사이클 발생")
else:
    print("사이클 없음")