Offline solution of Dynamic Connectivity Problem

그래프 이론에서 Dynamic Connectivity Problem은,

 * 1. 정점 u, v를 잇는 간선 추가

 * 2. 정점 u, v를 잇는 간선 제거 (이미 있다고 치자.)

 * 3. 그래프 상에서 두 정점이 연결되어 있는지 체크

와 같은 질의가 주어졌을 때, 이러한 질의를 빠르게 응답하는 방법을 찾는 문제이다.

O(Q|V|) 나 O(Q|E|) 정도에는, 기본적인 그래프 탐색 알고리즘으로도 아주 쉽게 풀수 있지만, 더 나은 복잡도를 내기는 쉽지 않은 문제이다. 2번 쿼리가 없다면 union-find data structure (링크) 를 사용해서 쉽게 풀 수 있지만, 더 복잡한 질의가 들어왔을 때는 쉬운 풀이가 존재치 않는다.

일반적인 경우 이 문제의 해법은 매우 어려워 보인다 (링크). 하지만, 오프라인 풀이 (질의에 그때그때 응답할 필요가 없고, 한번에 응답해도 괜찮은 풀이) 를 허용할 경우, 분할정복을 사용해서 해결할 수 있는 문제이다. 아주 쉬운 해법은 아니지만, 그래도 상당히 재미있는 아이디어들이 많아서 짚고 넘어갈 만한 방법인거 같다.

일단, 체크하는 쿼리에 순서대로 1, 2, 3 ... 등의 시간을 붙여놓고, 각각의 간선에 대해서 "lifetime"을 계산해 놓는다. 3번째 체크 쿼리가 들어오고, 2 - 3을 잇는 간선이 추가되고, 6번째 체크 쿼리가 들어오고, 2 - 3을 잇는 간선이 제거된다면. 2 - 3 간선의 lifetime은 [4, 6]의 구간이라고 해석되는 것이다.

이렇게 각각의 간선에 대해서 lifetime을 계산해두었을 때, 분할정복을 사용해서 문제를 해결할 수 있다. 체크 쿼리가 총 Q개라고 했을 때, Solve(1, Q, [lifetime이 계산된 간선 집합]) 을 호출하자.

Solve(S, E, edge set) :

 * 1. edge i의 lifetime을 [is, ie]라고 했을 때, is <= s && e <= ie인 간선들을 모두 union find에 추가.

 * 2. M = (S+E)/2 일때, 1의 조건을 만족치 않은 간선들 중...

     * 2.1 Solve(S, M, [S, M]과 lifetime이 겹치는 edge set)

     * 2.2 Solve(M+1, E, [M+1, E]와 lifetime이 겹치는 edge set)

 * 3. Union find 자료구조를, 1번 과정이 실행되기 전으로 rollback

3번이 가장 중요한 포인트이다. 3번 질의를 실행하기 위해서 :

 * path compression은 사용하지 않는다. 일단 롤백하기가 상당히 짜증나고. amortization이 잘 되는 지도 솔직히 잘 모르겠다.. 대신 rank compression을 사용한다. PS할때 rank compression은 과소평가되는 경향이 적잖이 있지만, 이것만 써도 O(lgN) complexity가 보장되니 나름 꿀방법이다.

 * 재귀 호출 내에 stack을 잡아서, 어떠한 변화를 줬는지를 기록해놓는다.

 * rollback 시에는 스택에서 pop해가면서 변화들을 원상복구해놓으면 된다.

시간 복잡도는 O(Qlg^2Q)이다. 구현 시 edge set을 그때그때 들고 다니지 않고 segment tree 스타일로 미리 전역에 박고 시작하면 깔끔하게 코딩할 수 있다. 시간 복잡도 분석도 훨씬 쉬워지고.

연습 문제 : http://codeforces.com/gym/100551/problem/A

내 솔루션 : http://codeforces.com/gym/100551/submission/18738804

여담으로, 문제는 다르지만, http://codeforces.com/contest/678/problem/F 문제도 비슷한 방법으로 풀린다. http://codeforces.com/contest/678/submission/18739573 (http://hongjun7.tistory.com/66. convex hull trick을 segment tree로 구성.)

+ 변종으로 Dynamic MST Problem도 있다. 이건 어떻게 풀지 ㅠㅠ 풀이를 아는대로 추가하겠다.

http://codeforces.com/blog/entry/16967