Dynamic Connectivity in Graph

http://codeforces.com/gym/100551

그래프에 대한 동적 연결성 문제들이다.

트리의 동적 연결성은 Link/Cut Tree 등으로 구현할 수 있으나 그래프에서는 상당히 어렵다…

Connect and Disconnect

그래프에서 간선을 추가하고 제거하는 연산이 있을 때, 컴포넌트의 개수를 구해야 한다.

$O(k \log k \log n)$ 오프라인으로 모든 간선들의 존재하는 기간 $[s, e]$ 를 계산한다. 제거되지 않는 간선은 마지막 쿼리 다음에 제거되는 것으로 본다.

기간 $[0, k + 1)$ 를 재귀로 분할 정복한다. 재귀 함수가 기간 $[x, y)$ 를 정복하고 있을 때는 다음과 같이 처리한다.

기간 $[x, y)$ 에 계속 살아있는 간선들을 모두 union-find로 추가한다.
$x = y$ 이고 $x$ 번째 쿼리가 ?라면 답을 출력한다.
$x < y$ 라면 현재 union-find 상태를 저장한 뒤 $[x, m)$ , $[m, y)$ 에 대해 재귀적으로 처리한다.

GraphAero

간선을 추가하는 연산이 있을 때, 단절선의 개수를 구해야 한다.

union find를 두 개 사용하는데, 1번은 connected component를 관리하고, 2번은 biconnected component를 관리한다. 또 노드들의 부모를 저장할 배열이 필요하다.

간선이 추가될 때, 두 가지 경우로 나뉜다.

간선이 두 컴포넌트를 연결하는 경우 두 컴포넌트의 트리를 연결하고 1번 union find에서도 연결한다.

큰 트리 밑에 작은 트리를 붙여서 크기 $A$ 와 $B$ 의 트리를 붙이는 연산을 $O(\min(A, B))$ 에 할 수 있다. 이때 시간복잡도는 $O(n \log n)$ 이다.

단절선의 개수는 1개 증가한다.

간선이 같은 컴포넌트의 두 점을 연결하는 경우

해당 컴포넌트에서 사이클이 생기며, 사이클 내의 모든 점이 하나의 BCC가 된다.

간선이 연결하는 두 점에서 LCA까지 올라가며 모든 점들을 합쳐준다. LCA를 빠르게 구할 필요는 없고, 두 점 중 깊이가 깊은 점을 한 칸 올리며 합치는 연산을 반복하면 시간복잡도는 한 번 올라갈 때마다 정점 하나가 없어지므로 amortized $O(n)$ 이 된다.

Bridges in a Tree

트리가 주어져 있는데, 여기에 몇 개의 간선을 추가했을 때 단절선의 개수를 구해야 한다. 각각의 쿼리는 독립적이다.

Heavy-Light Decomposition나 Link/Cut Tree 등을 이용하여 간선의 가중치에 단절선이면 $1$ , 아니면 $0$ 을 부여한다. 처음에는 트리이므로 모두 $1$ 이다. 간선 $(x, y)$ 가 들어오면 $x$ 부터 $y$ 까지의 경로가 단절선이 아니게 되므로, 모두 $0$ 로 만들어주며 트리 전체의 합을 따로 관리하여 출력하면 된다. 각 쿼리가 끝날 때마다 $0$ 으로 만들었던 경로를 다시 $1$ 로 만들면 $O(k_i \log n)$ 에 하나의 쿼리를 끝낼 수 있다. 총 시간복잡도는 $O(\sum k_i \log n)$ 이다.

Bridges: The Final Battle

간선을 추가하고 삭제하는 연산이 있을 때, 단절선의 개수를 구해야 한다.

단절선의 개수를 구하는 것을 단절선 길이의 총합을 구하는 것으로 생각하자. A번 문제와 비슷하게 분할 정복을 할 수 있다.

함수가 기간 $[x, y)$ 를 정복하고 있을 때

기간 $[x, y)$ 에 계속 살아있는 간선들을 인자로 넘겨받은 트리에 추가한 후, DFS를 통해 BCC들을 하나의 정점으로 압축한다.
남은 간선들의 정보를 압축된 정점의 정보로 갱신한다.
남은 간선들에 포함되어 있는 정점들로 트리 압축을 한다. 4-a. $x = y$ 라면 답을 출력한다. 4-b. $x < y$ 라면 $[x, m)$ , $[m, y)$ 에 대해서 재귀 함수를 호출한다. 넘겨주는 인자는 현재 가지고 있는 트리, 남은 간선들, 압축 후 정점의 개수이다.

트리 압축이 단절선의 총 길이를 바꾸지 않기 때문에 트리 압축을 할 수 있다. 남은 간선들이 $E$ 개라고 하면 트리 압축에서 사용된 정점은 최대 $2E$ 개이므로 트리 압축 후에 남는 정점은 최대 $4E$ 개로 $O(E)$ 가 된다. 각 간선들은 $O(\log k)$ 번 관여되므로 시간복잡도는 $O(k \log k)$ 가 된다.

Disconnected Graph

그래프가 주어져 있을 때, 4개 이하의 간선이 쿼리로 주어지는데, 이 간선들을 끊었을 때 그래프가 나뉘는지 판별해야 한다.

A 코드 가져다 쓰면 될 것 같은데… 잘 모르겠다. 확실한 건 A 코드 가져다 쓰는 것보다 나은 알고리즘이 있는 듯하다.