Union-Find 알고리즘

Union-Find의 개념

: Disjoint Set (서로소 집합)을 표현할 때 사용하는 알고리즘

Union-Find의 연산

make-set(x)

• 초기화
• x를 유일한 원소로 하는 새로운 집합 생성

union(x,y)

• 합하기
• x가 속한 집합과 y가 속한 집합을 합치는 연산

find(x)

• 찾기
• x가 속한 집합을 찾는 연산
• x가 속한 집합의 대표값 (=루트 노드 값) 반환

소스 코드

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

#두 집합 합치기
def union(a,b):
	a = find(a)
    b = find(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(a,b)
    
#각 원소가 속한 집합 출력
for i in range(1,v+1):
	print(find(i),end=' ')
print()

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

find 함수 부분을 아래 코드를 사용하면 시간 복잡도가 감소한다.

def find_parent(x):
	if parent[x] != x:
    	parent[x] = find_parent(parent[x])
    return parent[x]