트리의 동적 연결성은 Link/Cut Tree 등으로 구현할 수 있으나 그래프에서는 상당히 어렵다...
그래프에서 간선을 추가하고 제거하는 연산이 있을 때, 컴포넌트의 개수를 구해야 한다.
1) $O(klogklogn)$
오프라인으로 모든 간선들의 존재하는 기간 $[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(logk)$번 관여한다.
시간복잡도는 $O(klogklogn)$이다.
2) $O(klogk)$
1번과 똑같이 분할 정복을 하는데, 정복 단계에서 관여되는 정점의 수는 많아야 간선의 수의 2배라는 것을 이용한다.
함수가 기간 $[x, y)$를 정복하고 있을 때
1. 기간 $[x, y)$에 계속 살아있는 간선들을 빈 그래프에 추가한 후, DFS를 통해 연결 컴포넌트들을 하나의 정점으로 압축한다.
2. 남은 간선들의 정보를 압축된 정점의 정보로 갱신한다.
3. 어떠한 간선에도 포함되지 않는 정점들을 제외한다.
4-a. $x = y$이고 $x$번째 쿼리가 ?라면 답을 출력한다.
4-b. $x < y$라면 $[x, m)$, $[m, y)$에 대해서 재귀 함수를 호출한다. 넘겨주는 인자는 남은 간선들, 압축 후 정점의 개수, 관여되지 않아서 제외된 정점의 개수이다.
각 간선은 $O(logk)$번 관여되고, 관여되는 정점들은 간선의 2배이므로 $O(klogk)$개이다.
DFS의 시간복잡도는 정점과 간선의 개수의 합이므로 시간복잡도는 $O(klogk)$이다.
간선을 추가하는 연산이 있을 때, 단절선의 개수를 구해야 한다.
union find를 두 개 사용하는데, 1번은 connected component를 관리하고, 2번은 biconnected component를 관리한다.
또 노드들의 부모를 저장할 배열이 필요하다.
간선이 추가될 때, 두가지 경우로 나뉜다.
1. 간선이 두 컴포넌트를 연결하는 경우
두 컴포넌트의 트리를 연결하고 1번 union find에서도 연결한다.
큰 트리 밑에 작은 트리를 붙여서 크기 $A$와 $B$의 트리를 붙이는 연산을 $O(min(A, B))$에 할 수 있다.
이 때 시간복잡도는 $O(nlogn)$이다.
단절선의 개수는 1개 증가한다.
2. 간선이 같은 컴포넌트의 두 점을 연결하는 경우
해당 컴포넌트에서 사이클이 생기며, 사이클 내의 모든 점이 하나의 BCC가 된다.
간선이 연결하는 두 점에서 LCA까지 올라가며 모든 점들을 합쳐준다.
LCA를 빠르게 구할 필요는 없고, 두 점중 깊이가 깊은 점을 한칸 올리며 합치는 연산을 반복하면
시간복잡도는 한 번 올라갈 때마다 정점 하나가 없어지므로 amortized $O(n)$ 이 된다.
트리가 주어져 있는데, 여기에 몇 개의 간선을 추가했을 때 단절선의 개수를 구해야 한다.
각각의 쿼리는 독립적이다.
Heavy-Light Decomposition나 Link/Cut Tree등을 이용하여 간선의 가중치에 단절선이면 $1$, 아니면 $0$을 부여한다.
처음에는 트리이므로 모두 $1$이다.
간선 $(x, y)$가 들어오면 $x$부터 $y$까지의 경로가 단절선이 아니게 되므로,
모두 $0$로 만들어주며 트리 전체의 합을 따로 관리하여 출력하면 된다.
각 쿼리가 끝날 때마다 $0$으로 만들었던 경로를 다시 $1$로 만들면 $O(k_ilogn)$에 하나의 쿼리를 끝낼 수 있다.
총 시간복잡도는$O(\sum k_i logn)$ 이다.
간선을 추가하고 삭제하는 연산이 있을 때, 단절선의 개수를 구해야 한다.
단절선의 개수를 구하는 것을 단절선 길이의 총합을 구하는 것으로 생각하자.
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(logk)$번 관여되므로 시간복잡도는 $O(klogk)$가 된다.
그래프가 주어져 있을 때, 4개 이하의 간선이 쿼리로 주어지는데, 이 간선들을 끊었을 때 그래프가 나뉘는지 판별해야 한다.
