다양한 그래프 알고리즘(1) : 서로소 집합

수학에서 서로소 집합이란 공통 원소가 없는 두 집합을 의미한다.
예를 들어 {1, 2}와 {3, 4}는 서로소 관계이다.
반면에 {1,2}와 {2, 3}은 2라는 원소가 두 집합에 공통적으로 포함되어 있기 때문에 서로소 관계가 아니다.

서로소 집합 자료구조란, 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조 이다.
서로소 집합 자료구조는 union과 find 이 2개의 연산으로 구현할 수 있다.

아이디어 :

1. union(합집합) 연산을 확인하여, 서로 연결된 두 노드 A, B를 확인한다.
   1) A와 B의 루트 노드 A', B'를 각각 찾는다.
   2) A'를 B'의 부모 노드로 설정한다. (B'가 A'를 가리키도록)
2. 모든 union(합집합) 연산을 처리할 때까지 1. 과정을 반복한다.

서로소 집합 알고리즘 구현 :

# 조상 root를 찾을 때까지 재귀적으로 호출 + 
# 찾으러 가기 직전에 부모 테이블에 루트 노드를 update시키며 경로 압축
def find_parent(parent, data) :
    if parent[data] == data :
        return data
    parent[data] = find_parent(parent, parent[data])
    return parent[data]

# union 연산 수행
def union_parent(parent, a, b) :
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a < b :
        parent[b] = a
    else :
        parent[a] = b

# 노드 개수 : v, 간선 개수 : e
v, e = map(int, input().split())

# 부모 테이블 초기화
parent = [0] * (v+1)
for i in range(1, v+1) :
    parent[i] = i

# union 연산을 입력받아 수행
for i in range(e) :
    a, b = map(int, input().split())
    union_parent(parent, a, b)

print("[각 원소가 속한 집합] ", end= " ")
for i in range(1, v+1) :
    print(find_parent(parent, i), end=" ")

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

서로소 집합을 이용한 사이클 판별

서로소 집합은 무방향 그래프 내에서의 사이클을 판별할 때 사용할 수 있다.
(방향 그래프에서의 사이클 여부는 DFS를 이용하여 판별 가능)

아이디어 :

1. 각 간선을 확인하며 두 노드의 루트 노드를 확인한다.
   1) 루트 노드가 서로 다르다면 두 노드에 대하여 union 연산을 수행한다
   2) 루트 노드가 서로 같다면 사이클(Cycle)이 발생한 것이다.
2. 그래프에 포함되어 있는 모든 간선에 대하여 1. 과정을 반복한다.

사이클 판별 :

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

def union_parent(parent, a, b) :
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a < b :
        parent[b] = a
    else :
        parent[a] = b

# 노드 개수 : v, 간선 개수 : e
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) :
    a, b = map(int, input().split())
    if find_parent(parent, a) == find_parent(parent, b) :
        cycle = True
        break
    else :
        union_parent(parent, a, b)

if cycle :
    print("사이클 존재 O")
else :
    print("사이클 존재 X")