백준10364 Group of Strangers

문제 링크

• http://icpc.me/10364

시간복잡도

• $O(N + M \sqrt M)$

풀이

세 정점 $(u, v, w)$가 간선으로 연결되어 있는 경우의 수를 찾는 문제로 바꿔서 생각합시다. 간선 1개, 2개, 3개로 연결된 경우의 수를 각각 세서 더해주면 됩니다.

세 정점이 3개의 간선으로 연결된 경우의 수는 $O(M \sqrt M)$에 구할 수 있습니다.
차수가 $\sqrt M$ 이상인 정점을 무거운 정점, 그렇지 않은 정점을 가벼운 정점으로 정의합시다. 무거운 정점 2개를 연결하는 간선을 무거운 간선, 그렇지 않은 간선을 가벼운 간선으로 정의합시다. 악수 정리를 잘 생각해보면, 무거운 정점은 최대 $O(\sqrt M)$ 존재하는 것을 알 수 있습니다. 당연히 무거운 간선도 $O(\sqrt M)$개 존재합니다.
무거운 정점 3개와 무거운 간선 3개로 구성된 삼각형을 찾는 것은 Naive하게 구현하면 $O((\sqrt M)^3) = O(M \sqrt M)$에 구할 수 있습니다.
최소 1개의 정점이 가벼운 정점인 경우를 봅시다. 가벼운 간선이 잇는 두 정점 중 차수가 더 작은 정점을 $u$, 큰 정점을 $v$라고 합시다. $u$의 차수는 $\sqrt M$ 이하입니다.
$u$와 인접한 $w$를 모두 보면서, $u, v, w$가 모두 연결되어있는지 확인해주면 모든 경우의 수를 고려할 수 있습니다. 이 경우에는 시간 복잡도가 $O(M \times \sqrt M)$이 됩니다.

세 정점이 2개의 간선으로 연결된 경우의 수는 $O(N)$에 구할 수 있습니다.
차수가 $d$인 정점 $u$가 있을 때, $u$를 포함하는 세 정점 중 $u$는 2개의 간선과 연결되는 경우의 수는 $d(d-1)/2$입니다. ($u$와 인접한 서로 다른 두 정점 $v, w$ 선택) $v$와 $w$가 인접할 수 있기 때문에 세 정점이 간선 3개로 연결되는 경우의 수를 구해서 빼면 세 정점이 간선 1개로 연결되는 경우의 수가 나오게 됩니다.

세 정점이 1개의 간선으로 연결된 경우의 수는 $O(N)$에 구할 수 있습니다.
차수가 $d$인 정점 $u$ 있을 때, $u$를 포함하는 세 정점 중 $u$는 1개의 간선과 연결되는 경우의 수는 $d \times (N-d-1)$입니다. ($u$와 인접한 정점 $v$과 인접하지 않은 정점 $w$를 선택) $v$와 $w$가 인접할 수 있기 때문에 세 정점이 간선 2개로 연결되는 경우의 수를 구해서 빼면 세 정점이 간선 1개로 연결되는 경우의 수가 나오게 됩니다.