DCP (1) 썸네일형 리스트형 [CF] 100551A Connect and Disconnect 문제 링크: https://codeforces.com/gym/100551/problem/A 문제 설명: 정점 $n$개로만 이루어진 그래프에 $k$개의 쿼리가 주어지는데, 쿼리는 +, -, ? 이렇게 세 종류가 있다. +는 존재하지 않는 간선 하나를 추가하고, -는 이미 존재하는 간선 하나를 삭제한다. ?는 현재 그래프의 컴포넌트 개수를 출력한다. $n$과 $k$는 둘 다 30만 이하이다. 문제 풀이: - 쿼리가 오직 + 와 ?만 들어온다면...?Union-Find Tree를 이용해서 정점들을 쉽게 합쳐줄 수 있고, 시간복잡도는 $O(k alpha(k) )$가 되겠다. - 제거 쿼리가 추가되었을 때 만약에 정직하게 모든 쿼리들을 다 처리해 준다면...?Union-Find Tree를 그대로 첫번째 풀이에 적.. 이전 1 다음