사용자 도구

사이트 도구


ps:problems:boj:17398

통신망 분할

ps
링크acmicpc.net/…
출처BOJ
문제 번호17398
문제명통신망 분할
레벨골드 1
분류

Disjoint set

시간복잡도O(m*α(n))
인풋사이즈m<=100,000, n<=100,000
사용한 언어Python
제출기록63340KB / 376ms
최고기록344ms
해결날짜2022/06/24

풀이

  • 연결된 그래프에서 엣지를 삭제하는 쿼리들을 처리해야 할때, 오프라인 쿼리의 아이디어를 사용해서 역순으로 엣지를 추가해나가는 식으로 처리하는 것은 동적 연결성관련 문제에서 흔하게 사용되는 테크닉이다.
  • 이 문제도 마찬가지로 엣지를 추가하는 쿼리들로 바꿔서 처리할수 있고, 이렇게 두 그룹사이에 엣지를 추가해서 한 그룹으로 합치면서, 두 그룹의 크기를 계산해서 비용에 추가하는 것은 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()

토론

댓글을 입력하세요:
U W R​ A U
 
ps/problems/boj/17398.txt · 마지막으로 수정됨: 2022/06/24 16:55 저자 teferi