서로소 집합 서로소 집합은 집합 관계를 표현하는 자료구조로, 공통 원소가 없는 두 집합을 말한다. 서로소 집합 알고리즘은 union-find 연산으로 구성된다. 그래서 서로소 알고리즘을 union-find 알고리즘으로 부른다고도 한다. union(합집합 연산), find(찾기) union 연산은 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산이다. find 연산은 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산이다. union(x,y): x가 속한 집합과 y가 속한 집합을 합친다. find(x): x가 속한 집합의 대표 번호(루트 노드)를 반환한다. 1. union 연산을 확인하여 서로 연결된 두 노드 A,B를 확인한다. 1-1. A와 B의 루트 노드 A', B'를 찾는다 1-2. A'를..
코드 import sys sys.setrecursionlimit(10**5) # 재귀 깊이 제한 input = sys.stdin.readline # 빠른 입력 n,m = map(int, input().split()) set = [i for i in range(n+1)] # 부모 노드를 기록할 리스트 def find(a, parent): if a != parent[a]: # 루트 노드가 아니라면 parent[a] = find(parent[a], parent) # 루트 노드에 도달할 때까지 순회 return parent[a] # 루트 노드 반환 def union(a,b,parent): # 트리 합치기 a = find(a, parent) # 루트 노드 찾기 b = find(b, parent) if a < b:..
