Union-Find Algorithm (유니온 파인드 알고리즘) 탬플릿 코드

 

Union-Find Algorithm (유니온 파인드 알고리즘) 탬플릿 코드

n, m = map(int, input().split())

parent = [0] * (n + 1)
for i in range(n + 1):
    parent[i] = i


def find(node):
    if node != parent[node]:
        parent[node] = find(parent[node])  
    return parent[node]


def union(a, b, parent):
    pa = find(a)
    pb = find(b)

    if pa == pb:
        return
    
    if a > b:
        parent[pa] = pb
        
    else:
        parent[pb] = pa
        
for _ in range(m):
    u, v = map(int, input().split())
    union(u, v, parent)


for i in range(n + 1):
    find(i)

numbers = []
for i in range(len(parent)):
    if parent[i] not in numbers:
        numbers.append(parent[i])

print(len(numbers) - 1)

 

랭크 개념 추가

 

void union(int x, int y)
     xRoot = find(x);
     yRoot = find(y);
     if xRoot == yRroot
         return
 
     if (rank[xRoot] >= rank[yRoot])
         parent[yRoot] = xRoot;
     else
         parent[xRoot] = yRoot;
 
     if (rank[xRoot] == rank[yRoot])
         rank[yRoot] = rank[xRroot] + 1

 

 

종합 코드 ( 주석 추가)

n, m = map(int, input().split())

parent = [0] * (n + 1)
rank = [0] * (n + 1)  # 각 노드의 랭크(트리의 높이)를 저장하는 배열

# 초기화: 각 노드의 부모를 자기 자신으로 설정
for i in range(n + 1):
    parent[i] = i

def find(node):
    # 경로 압축: 재귀적으로 부모를 찾아가며 부모를 직접 최상위 부모로 변경
    if node != parent[node]:
        parent[node] = find(parent[node])  
    return parent[node]

def union(a, b):
    pa = find(a)  # a의 최상위 부모를 찾음
    pb = find(b)  # b의 최상위 부모를 찾음

    # 이미 같은 집합에 속해 있으면 아무 작업도 하지 않음
    if pa == pb:
        return
    
    # 랭크를 이용한 유니온: 항상 랭크가 낮은 트리를 랭크가 높은 트리에 연결
    if rank[pa] > rank[pb]:
        parent[pb] = pa
    elif rank[pa] < rank[pb]:
        parent[pa] = pb
    else:
        parent[pb] = pa
        rank[pa] += 1  # 랭크가 같은 경우 한쪽의 랭크를 증가시킴