그래프의 맥락에서 서로소 집합은 다음 문제를 직접 해결합니다:
문제. 처음에 비어 있는 그래프가 주어지며, 간선 추가(+)와 두 정점의 연결성 확인(?)으로 이루어진 쿼리 $n$개를 처리해야 합니다.
조금 생각해 보면 그 역문제도 풀 수 있습니다:
문제. 그래프가 주어지고, 미리 알려진 $n$개의 쿼리를 처리해야 합니다. 쿼리는 간선 삭제(-)와 두 정점의 연결성 확인(?)입니다.
여기서 핵심 조건은 모든 쿼리를 미리 알고 있다는 것입니다. 이 덕분에 모든 -를 +로 바꾸고 모든 쿼리를 역순으로 처리할 수 있습니다. 마지막에 그래프가 비게 된다면 이는 앞의 문제와 동일해지고, 그래프가 완전히 삭제되지 않는다면 삭제되지 않은 모든 간선을 맨 처음에 DSU에 추가하기만 하면 됩니다.
그러나 추가와 삭제가 동시에 있다면 문제는 훨씬 어려워집니다. 쿼리에 온라인으로 답해야 한다면 이를 위한 Lunk-Cut Tree라는 꽤 복잡한 자료구조가 있지만, 이 글에서는 다루지 않겠습니다. 그러나 쿼리를 미리 알고 있다면 이미 알고 있는 쿼리 분할 기법과 자료구조 롤백 기법을 적용할 수 있습니다.
#동적 연결성 문제
문제. 처음에 비어 있는 그래프가 주어지며, 간선 추가(+), 간선 삭제(-), 두 정점의 연결성 확인(?)으로 이루어진 $n$개의 미리 알려진 쿼리에 답해야 합니다.
쿼리에 대한 제곱근 분할법으로 문제를 풀어 봅시다. 쿼리들을 제곱근 크기의 블록으로 나누고, 각 블록마다 블록 전체에 걸쳐 존재하는 간선들만으로 DSU를 구축합니다.
각 쿼리에 답하기 위해 현재 블록에서 빠져 있는 모든 간선을 DSU에 추가하고, DSU에 직접 쿼리를 수행한 다음, 중요한 점은 현재 블록에서 수행한 모든 변경 사항을 롤백하여 깨끗한 DSU를 얻는 것입니다. 이렇게 얻은 DSU는 현재 블록의 다른 쿼리에도 같은 방식으로 사용할 수 있습니다.
DSU는 어떻게 롤백합니까? 초기화 트릭을 사용할 수도 있고(다만 여기서는 블록이 시작될 때의 DSU 상태가 「0」이 됩니다), 변경 사항의 목록을 유지하다가 그것을 역순으로 순회할 수도 있습니다.
다만 DSU 연산의 시간 복잡도는 조금 달라집니다. 최악의 경우 경로 압축을 통한 분할 상환은 이득을 주지 못합니다. 구조가 압축을 수행하게 한 다음 압축 이전 상태로 되돌리는 일을 여러 번 반복하게 만들 수 있기 때문입니다. 따라서 크기 또는 랭크 휴리스틱만 남게 되며, 이를 사용한 시간 복잡도는 $O(\log n)$입니다.
이러한 풀이는 $O(n \sqrt n \log n)$에 동작하지만, 더 빠르게 할 수 있습니다.
#쿼리에 대한 Divide-and-conquer
루트 휴리스틱 대신 재귀 함수 solve(l, r)을 만들어 봅시다. 이 함수는 구간 전체에 걸쳐 존재하는 모든 간선에 해당하는 DSU를 가진 상태에서 $l$번부터 $r$번까지의 모든 쿼리에 답합니다.
이 함수는 다음과 같이 동작합니다:
- 구간에 쿼리가 하나뿐이라면 DSU를 이용해 그 쿼리의 답을 구하고 종료합니다. 그렇지 않은 경우에는 다음과 같이 합니다.
- 시간 구간을 절반으로 나눕시다:
t = (l + r / 2). - 왼쪽 절반을 재귀적으로 해결합니다:
solve(l, t). - 쿼리의 오른쪽 절반 전체에 걸쳐 존재하는 간선들을 DSU에 추가합시다.
- 오른쪽 절반에 대해 재귀적으로 실행합니다:
solve(t, r). - DSU를 원래 상태로 롤백합니다.
재귀에 진입할 때와 재귀에서 빠져나올 때 해당 구간에 대해 DSU가 항상 깨끗한 상태라는 불변식을 항상 유지하므로, 알고리즘은 실제로 모든 쿼리에 답하며 $O(n \log^2 n)$에 동작합니다.
여기서 연결성에 특화된 것은 어디에도 사용하지 않았다는 점에 주목하십시오. 따라서 DSU가 지원하는 쿼리라면 무엇이든 답할 수 있습니다. 예를 들어 컴포넌트의 크기나 간선의 개수에 대한 쿼리도 가능합니다. 또한 다른 문제를 위한 변형도 존재합니다. 예를 들어 브리지나 이중 연결 컴포넌트를 찾는 문제가 있으며, 자세한 내용은 Сергей Копелиович의 졸업 논문에서 읽을 수 있습니다.