Dynamic Connectivity in Graph

http://codeforces.com/gym/100551

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

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

Connect and Disconnect
그래프에서 간선을 추가하고 제거하는 연산이 있을 때, 컴포넌트의 개수를 구해야 한다.
1. $O(k \log k \log n)$
  오프라인으로 모든 간선들의 존재하는 기간 $[s, e]$ 를 계산한다. (제거되지 않는 간선은 마지막 쿼리 다음에 제거되는 것으로 본다.
  기간 $[0, k + 1)$ 를 재귀로 분할 정복하는데, 재귀 함수를 자세히 설명하면
  함수가 기간 $[x, y)$ 를 정복하고 있을 때
  
  1. 기간 $[x, y)$ 에 계속 살아있는 간선들을 모두 union find로 추가한다.
  2-a. $x = y$ 이고 $x$ 번째 쿼리가 ?라면 답을 출력한다.
  2-b. $x < y$ 라면 $[x, m)$ , $[m, y)$ 에 대해서 재귀 함수를 호출한다.
  3. 1에서 추가한 간선들을 모두 삭제한다. (union find를 함수 호출 전으로 되돌린다.)
  
  union find를 되돌리기 위해서는 간선을 추가할 때 메모리의 변화를 모두 스택에 기록하고,
  간선을 제거할 때 스택에 저장된 변화를 되돌리면 된다.
  단, 되돌리기 연산 때문에 amortized되는 연산은 사용해서는 안된다. union find를 구현할 때 path compression은 하지 않고 union by rank만 해주면 된다.
  각 쿼리는 union find에 $O(\log k)$ 번 관여한다.
  시간복잡도는 $O(k \log k \log n)$ 이다.
2. $O(k \log k)$
  1번과 똑같이 분할 정복을 하는데, 정복 단계에서 관여되는 정점의 수는 많아야 간선의 수의 2배라는 것을 이용한다.
  
  함수가 기간 $[x, y)$ 를 정복하고 있을 때
  1. 기간 $[x, y)$ 에 계속 살아있는 간선들을 빈 그래프에 추가한 후, DFS를 통해 연결 컴포넌트들을 하나의 정점으로 압축한다.
  2. 남은 간선들의 정보를 압축된 정점의 정보로 갱신한다.
  3. 어떠한 간선에도 포함되지 않는 정점들을 제외한다.
  4-a. $x = y$ 이고 $x$ 번째 쿼리가 ?라면 답을 출력한다.
  4-b. $x < y$ 라면 $[x, m)$ , $[m, y)$ 에 대해서 재귀 함수를 호출한다. 넘겨주는 인자는 남은 간선들, 압축 후 정점의 개수, 관여되지 않아서 제외된 정점의 개수이다.
  
  각 간선은 $O(\log k)$ 번 관여되고, 관여되는 정점들은 간선의 2배이므로 $O(k \log k)$ 개이다.
  DFS의 시간복잡도는 정점과 간선의 개수의 합이므로 시간복잡도는 $O(k \log k)$ 이다.
GraphAero
간선을 추가하는 연산이 있을 때, 단절선의 개수를 구해야 한다.

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

간선이 추가될 때, 두가지 경우로 나뉜다.
1. 간선이 두 컴포넌트를 연결하는 경우
  두 컴포넌트의 트리를 연결하고 1번 union find에서도 연결한다.
  
  큰 트리 밑에 작은 트리를 붙여서 크기 $A$ 와 $B$ 의 트리를 붙이는 연산을 $O(\min(A, B))$ 에 할 수 있다.
  이 때 시간복잡도는 $O(n \log n)$ 이다.
  
  단절선의 개수는 1개 증가한다.
2. 간선이 같은 컴포넌트의 두 점을 연결하는 경우
  해당 컴포넌트에서 사이클이 생기며, 사이클 내의 모든 점이 하나의 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)$ 를 정복하고 있을 때
1. 기간 $[x, y)$ 에 계속 살아있는 간선들을 인자로 넘겨받은 트리에 추가한 후, DFS를 통해 BCC들을 하나의 정점으로 압축한다.
2. 남은 간선들의 정보를 압축된 정점의 정보로 갱신한다.
3. 남은 간선들에 포함되어 있는 정점들로 트리 압축을 한다.
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 코드 가져다 쓰는 것보다 나은 알고리즘이 있는 듯 합니다.

Dynamic Connectivity in Graph

코멘트

답글 남기기 응답 취소

더 많은 게시물

IOI 2011 Elephants

아쉬움이 남지만 (BOJ 18862)

국제 옥토끼 기구 (BOJ 17348)

제 2회 IDTcup 여담