서로소 집합

서로소 집합 Disjoint Sets
공통 원소가 없는 두 집합

서로소 집합 자료구조
서로소 판별을 위한 자료구조
서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조

서로소 집합 자료구조는 두 종류의 연산을 지원합니다
합집합 Union
두 개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산입니다.
찾기 Find
특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산입니다.

서로소 집합은 무방향 그래프 내에서의 사이클을 판별할 때 사용할 수 있다.

각 간선을 하나씩 확인하며 두 노드의 루트 노드를 확인한다
루트노드가 서로 다르다면 두 노드에 대하여 합집합연산을 수행
루트노드가 서로 같다면 사이클이 발생한 것이다