통신망 분할

• 연결된 그래프에서 엣지를 삭제하는 쿼리들을 처리해야 할때, 오프라인 쿼리의 아이디어를 사용해서 역순으로 엣지를 추가해나가는 식으로 처리하는 것은 동적 연결성관련 문제에서 흔하게 사용되는 테크닉이다.
• 이 문제도 마찬가지로 엣지를 추가하는 쿼리들로 바꿔서 처리할수 있고, 이렇게 두 그룹사이에 엣지를 추가해서 한 그룹으로 합치면서, 두 그룹의 크기를 계산해서 비용에 추가하는 것은 Disjoint Set을 이용해서 O(α(n))에 처리 가능하다.
• 풀이는 제거되지 않을 엣지들을 모두 추가해서 그룹들을 만들어놓고, 제거될 엣지들을 역순으로 추가하면서 비용을 계산하는 것이다. 총 m번의 union 연산이 필요하고, O(q)번의 사이즈 계산 연산이 필요하다. 각 연산은 모두 O(α(n))에 처리되고, q<m이므로 그냥 총 시간복잡도를 O(m*α(n)) 으로 쓸수 있다.

"""Solution code for "BOJ 17398. 통신망 분할".

- Problem link: https://www.acmicpc.net/problem/17398
- Solution link: http://www.teferi.net/ps/problems/boj/17398

Tags: [Disjoint set]
"""

import sys
from teflib import disjointset


def main():
    N, M, Q = [int(x) for x in sys.stdin.readline().split()]
    X_and_Y = [[int(x) for x in sys.stdin.readline().split()] for _ in range(M)]
    A = [int(sys.stdin.readline()) for _ in range(Q)]

    a_set = set(A)
    dsu = disjointset.ListDisjointSet(N)
    for i, (x_i, y_i) in enumerate(X_and_Y):
        if i + 1 not in a_set:
            dsu.union(x_i - 1, y_i - 1)
    answer = 0
    for i in reversed(A):
        x_i, y_i = X_and_Y[i - 1]
        x_set, y_set = dsu.find(x_i - 1), dsu.find(y_i - 1)
        if x_set != y_set:
            answer += dsu.size(x_set) * dsu.size(y_set)
            dsu.union(x_set, y_set)

    print(answer)


if __name__ == '__main__':
    main()

• Dependency: teflib.disjointset.ListDisjointSet