유니온 파인드

[백준 17398] 통신망 분할 (C++)

17398번: 통신망 분할 첫 번째 줄에는 통신탑의 개수인 자연수 N, 통신탑 사이의 연결의 개수인 자연수 M, 통신망 연결 분할 횟수인 자연수 Q가 공백으로 구분되어 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 100,000, 1 ≤ Q www.acmicpc.net 문제를 읽어보니 통신망들의 집합을 구현해야 했다. 서로 연결이 되어있는 통신망, 즉 하나의 정점으로 귀납되는 노드들 사이의 한 간선을 끊으면 2개로 나뉠 텐데 몇 개씩으로 나눠지는지를 구하면 된다. 풀이 방법을 떠올리기까지 꽤 오래 걸렸는데 처음에 노드의 간선을 끊는 동작을 하나의 쿼리로 보고 세그먼트 트리를 구성해서 풀어야 하나?라는 말만 그럴듯한 이상한 생각을 했다. 그러다가 일단 input에 입력을 다 받고 보니 반대로 생..