[BOJ17398] 통신망 분할

문제

• 건설된 통신망을 끊어 망분리 시키기
• 분리된 두 그룹에서 노드수만큼 곱하기

입력

• n, m, q
• m 개 줄에 노드 연결 x, y
• q 개 줄에 순서대로 끊을 a번째 연결

출력

• 첫 번째 줄에 Q개의 연결을 순서대로 제거하는데 드는 비용의 합을 출력한다.

설계

• 유니온파인드를 이용해 각 그룹의 노드 수 체크
• 끊어야할 edge 빼고 다 연결
• 끊어야할 순서 반대로 망 분리되는지 확인해가며 노드 수 곱해주기

피드백

• 유니온 파인드를 공식화해두고 잊어버리지 않도록 체화하기
• 유니온의 수를 탐색하는 것은 수에 대한 배열을 하나 더 만들어 parent 배열과 연동
• 답이 굉장히 큰 수가 될 수 있어서 long long 타입으로 쓰기. 이 부분 자주 놓침

How I solved(click to github)

---

ref :
BOJ17398