서로소 집합 자료구조:

• 서로소 부분 집합(disjoint set)들로 나누어진 원소들의 데이터를 처리하기위한 자료구조
• 구현 시 트리 자료구조를 이용하여 집합을 표현
• 합집합(union) 연산, 찾기(find) 연산

서로소 집합 알고리즘:

• 1. 합집합 연산을 확인하여, 서로 연결된 두 노드(A, B)를 확인
  • 1. A, B 각각의 루트노드 A', B'을 각각 찾음
  • 2. A'를 B'의 부모 노드로 설정한다(=B'가 A'을 가르킴)
• 2. 모든 합집합 연산을 처리할 때까지 1번의 과정을 반복

서로소 집합 알고리즘 시간 복잡도:

• 경로압축 기법 사용 시 : $O(V + M(1+log_{2-M/V} V))$
  • 노드 개수: $V$
  • 합집합 연산 개수: $V-1$
  • 찾기 연산 개수: $M$

#p.298 "이코테" 실전문제 <2> 팀 결성

# 이 부분은 특히 경로압축 기법이 쓰인거니 다시 봐보자 p.275
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

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

parent = [0] * (n + 1)

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

for i in range(m):
    oper, a, b = map(int, input().split())
    if oper == 0:
        union_parent(parent, a, b)

    elif oper == 1:
        if find_parent(parent, a) == find_parent(parent, b):
            print('YES')
        else:
            print('NO')

추가

경로압축 기법을 제외 하더라도 시간 복잡도를 줄일 수 있는 방법은 더 있음