[알고리즘] UNION FIND(서로소 집합 알고리즘)

union find(=서로소 집합 알고리즘)

• union 연산 : 2개의 원소가 포함된 집합을 하나의 집합으로 합침
• find 연산 : 특정한 원소가 속한 집합이 어떤 집합인지 알려줌
• 서로소 집합은 트리 구조를 이용해 표현하며, 부모 테이블을 항상 가지고 있어야 함
• 무방향 그래프에서 사이클 판별 가능 => 두 노드의 루트 노드가 같으면 cycle

 

union find 코드

def find_parent(parent, x): #루트노드가 바로 부모노드가 됨 => 경로압축
  if parent[x] != x:
    parent[x] = find_parent(parent, parent[x])
  return parent[x]
  
def find_parent1(parent, x): #부모노드가 제대로 출력 => 경로압축 x
  if parent[x] != x:
    return find_parent(parent, parent[x])
  return 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

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=" ")

 

관련 문제

 

백준 1717 집합의 표현 O (골드5)

백준 1976 여행가자 O (골드4)

백준 16562 친구비

백준 4195 친구 네트워크

백준 14868 문명

백준 3197 백조의 호수

백준 11085 군사 이동

백준 9938 방 청소

백준 10775 공항