3 super coloring

반대 그래프를 직접 생각하면 조건이 복잡해 보일 수 있다. 원래 그래프에서 두 정점 $u, v$의 관계를 기준으로 조건을 다시 쓰자.

반대 그래프에서 간선으로 연결된 두 정점은 서로 다른 색이어야 한다. 이는 원래 그래프에서 간선으로 연결되어 있지 않은 두 정점은 서로 다른 색이어야 한다는 뜻이다.

반대 그래프에서 간선으로 연결되어 있지 않은 두 정점은 서로 같은 색이어야 한다. 이는 원래 그래프에서 간선으로 연결된 두 정점은 서로 같은 색이어야 한다는 뜻이다.

따라서 원래 그래프에서는 다음 조건이 성립해야 한다.

• 간선으로 연결된 두 정점은 같은 색이어야 한다.
• 간선으로 연결되어 있지 않은 두 정점은 서로 다른 색이어야 한다.

이 조건으로부터, 같은 연결 요소 안의 모든 정점은 같은 색이어야 한다. 왜냐하면 간선을 따라 이동할 때마다 색이 같아야 하기 때문이다.

또한 같은 색을 가진 두 정점은 반드시 간선으로 연결되어 있어야 한다. 그러므로 각 연결 요소는 완전 그래프여야 한다.

결국 조건은 다음과 동치이다.

• 원래 그래프의 연결 요소 개수가 $3$개 이하이다.
• 모든 연결 요소가 완전 그래프이다.

연결 요소는 DSU 또는 DFS/BFS로 구할 수 있다. 어떤 연결 요소의 크기가 $k$라면, 그 연결 요소가 완전 그래프이기 위한 필요충분조건은 그 안의 모든 정점의 차수가 정확히 $k-1$인 것이다.

따라서 모든 간선을 DSU로 합친 뒤, 각 연결 요소의 크기를 구한다. 연결 요소가 $3$개보다 많으면 불가능하다. 그렇지 않다면 각 정점 $v$에 대해

$$\deg(v) = \operatorname{size}(\operatorname{component}(v)) - 1$$

인지 확인한다. 모든 정점이 이 조건을 만족하면 가능하고, 각 연결 요소에 서로 다른 색을 배정하면 된다.

시간 복잡도는 $O((n+m)\alpha(n))$이고, 메모리 사용량은 $O(n+m)$이다.