Dynamic Connectivity in Graph http://codeforces.com/gym/100551 그래프에 대한 동적 연결성 문제들이다.트리의 동적 연결성은 Link/Cut Tree 등으로 구현할 수 있으나 그래프에서는 상당히 어렵다... 그래프에서 간선을 추가하고 제거하는 연산이 있을 때, 컴포넌트의 개수를 구해야 한다. 1) $O(klogklogn)$오프라인으로 모든 간선들의 존재하는 기간 $[s, e]$를 계산한다. (제거되지 않는 간선은 마지막 쿼리 다음에 제거되는 것으로 본다.기간 $[0, k + 1)$를 재귀로 분할 정복하는데, 재귀 함수를 자세히 설명하면함수가 기간 $[x, y)$를 정복하고 있을 때1. 기간 $[x, y)$에 계속 살아있는 간선들을 모두 union find로 추가한다.2-a. $x = y$이고 $x$번째 쿼리가 .. 더보기 이전 1 ··· 13 14 15 16 17 18 19 ··· 24 다음