언제 쓰는가

• 그래프에서 두 노드 사이에 사이클이 존재하는지 확인할 때 사용함
• 이어질 크루스칼 알고리즘에서 사용됨

기본 구현

import sys
input = sys.stdin.readline

def find(x): # 어떤 노드가 주어질 때 이 요소의 루트 노드를 찾는 연산 (== 원소가 속한 집합을 알려줌)
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]

def union(a, b): # 두 개의 집합을 하나로 합치는 연산
    a = find(a)
    b = find(b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

v, e = list(map(int, input().rstrip().split())) # 노드 개수, 간선 개수
parent = [0] * (v + 1)

for i in range(1, v + 1): # 최초 부모 테이블은 본인으로 초기화
    parent[i] = i

for i in range(e): # union-find 연산 수행
    a, b = list(map(int, input().rstrip().split())) # 연결되어 있는 간선
    union(a, b)

사이클 유무 확인법

for i in range(e):
    a, b = list(map(int, input().rstrip().split()))
    cycle = False
    if find(a) == find(b):
        cycle = True
    else:
        union(a, b)

마지막에 연산 수행을 이렇게해주면 됨