[알고리즘] Union-Find

유니온파인드 알고리즘이란

✔ 서로소 집합(Disjoint Set)
✔ 여러 개의 노드가 존재할 때 , 임의의 두 노드가 같은 그래프에 속해있는지 판별

Union & Find

• Find
  노드 x가 포함된 집합을 찾는 연산

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

• Union
  노드 x가 포함된 집합과 노드 y가 포함된 두 집합을 통합하는 연산

def  union_parent(parent, x, y):
     x = find_parent(parent, x)
     y = find_parent(parent, y)
     # 단순한 형태에서는 작은 쪽으로 합친다.
     if  x < y:
         parent[y] = x
     else:
         parent[x] = y

코드 예시

# 노드와 간선(union 연산) 개수
node, edge = map(int, input().split())

# 0으로 부모 배열 초기화
parent = [0  for  _  in  range(node + 1)]

# 부모를 자기 자신으로 초기화
for  i  in  range(1, node + 1):
parent[i] = i


# union 연산
for  i  in  range(edge):
a, b = map(int, input().split())
union_parent(parent, a, b)


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


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

최적화

경로 압축 (Path compression)

# 경로 압축 -> 부모값 재귀적으로 갱신
def  find_parent_compression(parent, node):
    if  parent[node] != node:
        parent[node] = find_parent_compression(parent, parent[node])
    return  parent[node]

Rank 이용 (Union by Rank)

# rank: 각 노드의 rank를 저장할 리스트
rank = [0 for _ in range(N + 1)]

# def union_parent_rank(x, y):
    x = find_parent(x)
    y = find_parent(y)
    if x == y:
        return
    # 랭크가 낮은 집합을 높은 집합으로 병합해준다
    if rank[x] > rank[y]:
        parent[y] = x
    else:
        parent[x] = y
        # 랭크가 동일할 경우
        if rank[x] == rank[y]:
            rank[y] += 1

코드 예시

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


def union_parent(x, y):
    x = find_parent(x)
    y = find_parent(y)
    if x == y:
        return
    if rank[x] > rank[y]:
        parent[y] = x
    else:
        parent[x] = y
        if rank[x] == rank[y]:
            rank[y] += 1


# 노드와 간선(union 연산) 개수 
node, edge =  map(int,  input().split())  
# 0으로 부모 배열 초기화 
parent =  [0  for _ in  range(node +  1)]
# 1로 랭크 초기화
rank = [1 for _ in range(node + 1)]

# 부모를 자기 자신으로 초기화
for  i  in  range(1, node + 1):
    parent[i] = i

# union 연산
for  i  in  range(edge):
    a, b = map(int, input().split())
    union_parent(a, b)

# 각 원소가 속해있는 집합 출력
for  i  in  range(1, node + 1):
    print(find_parent(i), end=' ')
print()

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

Weighted Union Find

✔ parent 배열이 음수일 경우 부모노드로서 음수의 절댓값이 size(rank)가 되고, 양수일 경우 부모노드를 가리킨다

parent = [-1 for _ in range(N + 1)]

def find_parent(x):
    if parent[x] < 0:
        return x
    p = find(parent[x])
    parent[x] = p
    return p

def union_parent(x, y):
    x = find_parent(x)
    y = find_parent(y)

    if x == y:
        return

    if parent[x] < parent[y]:
        parent[x] += parent[y]
        parent[y] = x
    else:
        parent[y] += parent[x]
        parent[x] = y