서로소 집합 자료구조

강의 링크

(이코테 2021 강의 몰아보기) 8. 기타 그래프 이론

목표

어떤 집합에서 어떤 무리들이 있는지 확인하는 알고리즘인 유니온 파인드를 구현.

위의 그림처럼 노드들이 주어지고 (방향성이 없는) 엣지들이 주어졌을때 빨간 동그라미로 묶인 무리들이 어떻게 구성되어있는지 출력하는 것이 목표.

알고리즘

노드 각각의 부모 노드가 무엇인지 확인해주는 parent 집합을 노드의 개수만큼 할당해주고 처음엔 노드 자신들이 들어간다. 다음 엣지들을 입력받으면서 한단계 한단계 나아간다.

코드(동빈나님의 강의에서 가져옴)

import sys

# 특정 원소가 속한 집합을 찾기
def find_parent(parent, x):
    #루트 노드를 찾을 때까지 재귀 호출
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

# 두 원소가 속한 집합을 합치기
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 = 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) 루트 노드가 서로 다르다면 두 노드에 대하여 Union연산을 수행.
2) 루트 노드가 서로 같다면 사이클이 발생한 것.
나. 그래프에 포함되어 있는 모든 간선에 대해서 "가"연산을 반복.

코드(동빈나님의 강의에서 가져옴)

import sys

# 특정 원소가 속한 집합을 찾기
def find_parent(parent, x):
    #루트 노드를 찾을 때까지 재귀 호출
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

# 두 원소가 속한 집합을 합치기
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

# 노드의 개수와 간선(Union 연산)의 개수 입력 받기
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
    # 사이클이 발생하지 않았다면 합집합(Union) 연산 수행
    else:
        union_parent(parent, a, b)

if cycle:
    print("사이클이 발생했습니다.")
else:
    print("사이클이 발생하지 않았습니다.")