PROBLEM LINK:
Author: Zi Song Yeoh
DIFFICULTY:
EASY
PREREQUISITES:
Graph Theory, DFS/BFS
PROBLEM:
You are given a graph of n vertices. Initially, all pairs of vertices are connected by an edge. However, m pairs of edges were deleted. Some of the vertices are colored by white or black. Determine the number of ways to color the remaining vertices by white or black so that the subgraph formed by vertices of each color is a complete graph.
QUICK EXPLANATION:
The trick is to consider the complement graph, i.e. the graph with n vertices and m edges. The key observation is that the endpoints of an edge in the new graph cannot have the same color. Otherwise, in the original graph, we’ll have two same color vertices with no edge between them. Now, we consider each connected component of the new graph seperately. We have to color the vertices so that each edge has distinct-colored endpoints. Consider a connected component. If one of its vertices has been colored, then the colors of the remaining vertices are uniquely determined as well. We can check whether the colors are correct by a single dfs/bfs. If none of the vertices has been colored, and the component is bipartite (which we can check with a dfs/bfs), then there are 2 ways to color this component. In the end, multiply all the answers for each component.
EXPLANATION:
Subtask 1 can be solved by enumerating all possibilities of coloring the vertices. However, one has to be careful when checking whether a coloring is feasible. The naive way works in O(2^{n} \cdot n^{2}), which might or might not pass the TL. A faster way which makes it possible to check whether a coloring is feasible in O(m + n) comes from the following observation :
If we consider the graph where the missing edges are the edges of the graph, then any two adjacent vertices in the new graph must have different color.
Armed with this fact, we can check whether a coloring works by a single dfs/bfs on the graph.
The solution to subtask 2 is also based on the above fact. The thing is, we can’t afford to try all possible colorings. Let’s analyze the graph closely. It is made up of some connected components. Clearly, we can consider each connected component seperately and multiply the results of each component together. It remains to know how to calculate the answer for a single component.
To calculate the answer for each component, we note that once the color of one vertex is determined, the remaining vertices will automatically have its color determined. (and this can be found by a dfs/bfs) So, the solution is simple. For each component select a vertex, and try both possible colors and see if the whole component can be colored correctly. Then, multiply the answer for each component. The whole answer can thus be calculated by a single dfs/bfs, so the complexity is O(n + m), which passes easily.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.