BOJ 1741 - 반 나누기

BOJ 1741 - 반 나누기

이 문제는 사실상 $O(N^2)$개의 간선이 존재할 때 연결 그래프의 구성을 구하는 문제이다.

간선이 $N(N-1) / 2-M$ 개가 있다고 보면 된다.

그러나 이건 너무 많기 때문에 일반적인 방법으로 구할 수 없다.

이런류의 문제들은 대개 그래프의 성질을 이용해서 시간복잡도를 특이하게 줄이는 방법을 고민해봐야 한다.

예를 들어, Small to Large 알고리즘 같은 느낌과 비슷한 것 같다.

그런식으로 접근했지만 쉽게 풀 수 없었다.

가장 간선의 개수가 작은 정점의 번호를 $s$라고 하자.

$s$가 가진 간선의 개수는 최대 $O(M / N)$이다. 그렇지 않다면 $s$가 가장 간선이 적다는 것에 모순이다.

$s$와 이어진 그룹을 $B$, 간선으로 이어지지 않은 그룹을 $A$라 하자.

$s$는 $A$의 모든 정점들과 DSU로 잇는다.

$B$는 최대 $O(M/N)$ 개의 정점이 있다.

$B$에서 $\{s\} + A$의 모든 정점들을 보고 간선이 연결되어있지 않은것이 있다면 이어준다. 이 과정이 $O(\dfrac MN \cdot N \log M)$ 이다.

$B$에서 $B$들 끼리 연결되지 않은 것이 있는지 완전 탐색으로 $O(n(B)^2)$ 로 검사한다. 이 과정이 $O\Bigl( \left( \dfrac MN \right)^2 \log M\Bigr)$ 이다.

즉, 이렇게 특이하게 정점을 분리하고 시작하는 것으로 시간복잡도를 줄여 문제를 해결할 수 있다.