서로소 집합 알고리즘

1. 서로소 집합
2. 예시
3. 코드

1. 서로소 집합

서로소 집합은 공통 원소가 없는 두 집합이다.

1. union(합집합)연산을 확인해서 서로 연결된 두 노드 A,B를 확인한다.
2. A를 B의 부모 노드로 설정한다. (B→A)
3. 모든 union (합집합) 연산을 처리 할 때까지 1번 과정을 반복한다.

밑에서 과정을 보도록하자.

전체 집합: {1,2,3,4,5,6}

• union 1,4
  union 2,3
  union 2,4
  union 5,6

union연산은 두 노드가 같은 집합에 속한다는 것을 의미하고, 같은 집합에 속한 두 노드는 간선으로 연결된다. 일반적으로 서로소집합을 그림으로 표현할 때는 번호가 큰 노드가 작은 노드를 간선으로 가르키는 형태로 표현된다.

2. 예시

3. 코드

def find_parent(x, parent):
    if parent[x] != x:  # 부모가 자기 자신이 아닐 경우
        parent[x] = find_parent(parent[x], parent)  # 경로 압축
    return parent[x]

def union(a, b, parent):
    a = find_parent(a, parent)
    b = find_parent(b, parent)
    if a < b:
        parent[b] = a  # b의 부모를 a로 설정
    else:
        parent[a] = b  # a의 부모를 b로 설정

# 노드 갯수, 간선 갯수
v, e = map(int, input().split())
parent = [i for i in range(v + 1)]  # 각 노드의 부모를 자기 자신으로 초기화

for _ in range(e):
    a, b = map(int, input().split())
    union(a, b, parent)

# 각 원소가 속한 집합 출력
for i in range(1, v + 1):
    print(find_parent(i, parent), end=' ')

print() 

# 부모 테이블 출력
for i in range(1, v + 1):
    print(parent[i], end=' ')