알고리즘
[알고리즘] Union-Find(유니온 파인드)로 무방향 그래프에서 사이클(cycle) 찾기
1️⃣ 유니온 파인드란?Union-Find는 서로소 집합을 찾는 알고리즘으로, 서로소 집합은 공통 원소가 없는 두 집합을 의미한다. 아래와 같이 루트 노드를 찾고(find), 연결된 두 노드를 합치는(union) 연산으로 이루어져 있다.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 2️⃣ 유니온 파인드로..
