BOJ 26971 - Strongest Friendship Group

May 16, 2023

$c$ 를 그룹의 크기라고 한다면 $c \le 650$ 임을 관찰한다. $\dfrac{n(n+1)}2 \le M$ 이여야 하기 때문이다.

따라서 Disjoint Set을 안쓰고도 적절히 최적화해서 통과할 수 있다.

우선 $c$ 를 증가시켜나가며 정점들을 제거해나간다.

제거되지 않은 것들 중 $\text{degree}_i < c$ 인 것들을 큐에 넣고 제거하고 인접한 것들도 degree를 줄여주고 반복한다.

이제 각 $c$ 마다 DFS를 돌리면 문제를 $O(N \cdot \sqrt{ M })$ 에 해결하게 되는데, 이건 간당간당하다. 실제로 TLE가 났다.

좀 더 최적화를 해주기 위해 이전 DFS의 결과가 $0$ 이 아니라면 $c$ 가 증가함에 따라 어떠한 정점도 제거되지 않은 경우 이전의 DFS의 결과를 그대로 사용해주는 최적화로 해결해줄 수 있다.

USACO 정해 1Permalink

$v$ 를 가장 작은 degree를 가진 노드라고 하자.

만약 최적의 friendship group이 $v$ 를 포함한다면 group은 $v$ 를 포함한 연결 그래프의 subset이다.

따라서 어떤 group의 정답은 $v$ 의 degree수 * $v$ 의 연결 컴포넌트이다.

$v$ 가 최소 degree를 갖기 때문에 $v$ 의 연결 그래프 자체가 friendship graph가 된다.

만약 최적의 friendship group이 $v$ 를 포함하지 않는다면 $v$ 를 graph에서 제거해준다.

반복적으로 그래프에서 가장 작은 degree를 가진 $v$ 를 결정해준다.

이 과정은 $O(M+N)$ 이 걸리는데, 연결 그래프의 노드수를 세는것은 $O(MN)$ 이 걸리므로 최적화가 필요하다.

이 과정을 반대로 진행하며 Disjoint Set을 쓰며 최적화가 가능하다.

가장 작은 degree를 가진 $v$ 를 제거해나가는게 아니라 가장 큰 degree를 가진 $v$ 를 삽입해가며 Disjoint Set으로 집합의 크기를 갱신한다.

내 풀이대로 루트질을 이용하여 푼다.