3 Super Coloring

Thinking directly about the complement graph may look complicated. Instead, rewrite the conditions in terms of the original graph.

If two vertices are adjacent in the complement graph, they must have different colors. This means that two non-adjacent vertices in the original graph must have different colors.

If two vertices are non-adjacent in the complement graph, they must have the same color. This means that two adjacent vertices in the original graph must have the same color.

So in the original graph, the following must hold.

• Adjacent vertices must have the same color.
• Non-adjacent vertices must have different colors.

From this, all vertices in the same connected component must have the same color, because colors must remain the same along every edge.

Also, any two vertices with the same color must be adjacent. Therefore, every connected component must be a clique.

Thus, the condition is equivalent to the following.

• The original graph has at most $3$ connected components.
• Every connected component is a complete graph.

We can find connected components using DSU or DFS/BFS. If a connected component has size $k$, it is a clique if and only if every vertex in it has degree exactly $k-1$.

So we merge all edges using DSU, compute the size of each component, and check the number of components. If there are more than $3$, the answer is impossible. Otherwise, for every vertex $v$, check whether

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

holds. If all vertices satisfy this condition, the answer is possible, and we assign one color to each connected component.

The time complexity is $O((n+m)\alpha(n))$, and the memory usage is $O(n+m)$.