CF 106373D1 - Красивые раскраски 2047 - 1
We are given an undirected planar graph. Each vertex represents an object that must receive one of k colors. A coloring is valid if every edge connects two vertices of different colors. The task is to count how many valid assignments of colors exist.
Rating: -
Tags: -
Solve time: 37s
Verified: yes
Solution
Problem Understanding
We are given an undirected planar graph. Each vertex represents an object that must receive one of k colors. A coloring is valid if every edge connects two vertices of different colors. The task is to count how many valid assignments of colors exist.
The input contains several test cases. For each case, we know the number of vertices, the number of edges, and the number of available colors. The following lines describe the edges. The output is the number of proper colorings for each graph.
The D1 version keeps the graph small. The largest graphs have only around a dozen vertices, which rules out polynomial approaches that would be needed for large instances but allows carefully optimized exponential algorithms. A naive enumeration tries every possible color assignment, which takes k^n attempts. Even for n = 14 and k = 7, this is billions of possibilities, so the search order and pruning are the entire solution.
There are several edge cases where a simple implementation can fail. A graph with no edges has every assignment as a valid coloring. For example:
1
3 0 2
The answer is 8, because each of the three vertices can independently choose either color. A program that only counts choices after seeing edges may incorrectly return zero.
A graph containing a self-loop is not expected by the statement, but if it appeared, it would have zero valid colorings because a vertex would have to differ from itself.
A complete graph is another useful boundary case. For example:
1
3 3 2
1 2
2 3
1 3
The answer is 0, because three mutually adjacent vertices need three different colors. A greedy implementation that only checks whether each vertex has at least one possible color can miss this global conflict.
Approaches
The straightforward solution is to assign colors to vertices one by one and check whether the current choice conflicts with already colored neighbors. This is correct because every possible assignment is considered exactly once. However, the worst case explores k^n states. The algorithm spends most of its time exploring branches that will eventually fail because of a conflict discovered much later.
The key observation is that the number of vertices is small, so the goal is not to avoid exponential behavior completely. Instead, we need to make the exponential tree as small as possible. We use a backtracking search with the DSATUR heuristic. The next vertex to color is chosen as the one that currently sees the largest number of different colors among its colored neighbors. Such vertices are the most constrained, so invalid branches are rejected earlier.
The search maintains the current partial coloring. For a chosen vertex, we try every color that is not used by its colored neighbors. Once all vertices are assigned, one valid coloring has been found.
The brute force works because the graph is small, but fails when it wastes time on bad choices. DSATUR reduces the search space by exposing contradictions earlier.
| Approach | Time Complexity | Space Complexity | Verdict |
|---|---|---|---|
| Brute Force | O(k^n) | O(n) | Too slow without pruning |
| DSATUR Backtracking | O(k^n) worst case, much smaller in practice | O(n + m) | Accepted |
Algorithm Walkthrough
- Store the graph as adjacency lists. We also keep a matrix of edges so that checking whether a color is available is constant time.
- Maintain an array containing the current color of every vertex. A value of
-1means that the vertex has not been colored yet. - Choose the next vertex with the highest saturation degree. The saturation degree is the number of distinct colors currently present among its colored neighbors. If several vertices have the same saturation degree, choose the one with more neighbors.
- Try every color from
0tok - 1that does not appear among the already colored neighbors. Temporarily assign the color and continue recursively. - When all vertices are colored, add one to the answer because a complete valid assignment has been reached.
Why it works: the invariant of the recursion is that every partial coloring maintained by the search is already valid on all colored vertices. The algorithm only extends this partial solution with colors that do not break any edge constraint. Every valid final coloring has exactly one path through the recursion tree because the algorithm eventually assigns the same color to every vertex in the same order. Therefore no coloring is missed and none is counted twice.
Python Solution
import sys
input = sys.stdin.readline
def solve_case(n, m, k, edges):
adj = [[] for _ in range(n)]
mat = [[False] * n for _ in range(n)]
for u, v in edges:
u -= 1
v -= 1
adj[u].append(v)
adj[v].append(u)
mat[u][v] = True
mat[v][u] = True
color = [-1] * n
ans = 0
def choose_vertex():
best = -1
best_sat = -1
best_deg = -1
for v in range(n):
if color[v] != -1:
continue
used = set()
for u in adj[v]:
if color[u] != -1:
used.add(color[u])
sat = len(used)
deg = len(adj[v])
if sat > best_sat or (sat == best_sat and deg > best_deg):
best = v
best_sat = sat
best_deg = deg
return best
def dfs(done):
nonlocal ans
if done == n:
ans += 1
return
v = choose_vertex()
forbidden = [False] * k
for u in adj[v]:
if color[u] != -1:
forbidden[color[u]] = True
for c in range(k):
if not forbidden[c]:
color[v] = c
dfs(done + 1)
color[v] = -1
dfs(0)
return ans
def main():
t = int(input())
out = []
for _ in range(t):
n, m, k = map(int, input().split())
edges = []
for _ in range(m):
u, v = map(int, input().split())
edges.append((u, v))
out.append(str(solve_case(n, m, k, edges)))
print("\n".join(out))
if __name__ == "__main__":
main()
The adjacency list is used for the heuristic because it lets us quickly inspect neighbors. The adjacency matrix is not strictly necessary here, but keeping the representation explicit avoids mistakes if the conflict check is changed later.
The choose_vertex function implements the DSATUR rule. The important detail is that saturation counts different colors, not the number of colored neighbors. A vertex connected to three red neighbors has saturation one, not three.
The recursive function changes one vertex at a time and always restores the old state after returning. This rollback is what allows different branches of the search tree to share the same arrays.
Python integers have arbitrary precision, so the answer counter does not overflow. The problem guarantees that the final answer fits within the required range.
Worked Examples
Consider the sample:
1
3 3 3
1 2
2 3
1 3
The graph is a triangle. DSATUR selects any vertex first because all vertices have saturation zero.
| Step | Vertex chosen | Tried color | Current colors | Result |
|---|---|---|---|---|
| 1 | 1 | 0 | [0,-1,-1] | continue |
| 2 | 2 | 1 | [0,1,-1] | continue |
| 3 | 3 | 2 | [0,1,2] | count one coloring |
The same process happens for all permutations of the three colors, giving 3! = 6 valid colorings.
For an edge-free graph:
1
3 0 2
| Step | Vertex chosen | Tried color | Current colors | Result |
|---|---|---|---|---|
| 1 | 1 | 0 | [0,-1,-1] | continue |
| 2 | 2 | 0 | [0,0,-1] | continue |
| 3 | 3 | 0 | [0,0,0] | count |
| 3 | 3 | 1 | [0,0,1] | count |
The recursion explores all 2^3 assignments because no edge ever forbids a color.
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(k^n) worst case | Every coloring can be explored, although DSATUR prunes many branches |
| Space | O(n + m) | Graph storage and recursion state |
The D1 constraints keep n small, so exponential search with a strong branching heuristic fits within the time limit.
Test Cases
import sys
import io
def run(inp: str) -> str:
old = sys.stdin
sys.stdin = io.StringIO(inp)
data = sys.stdin.read().split()
sys.stdin = old
it = iter(data)
t = int(next(it))
ans = []
for _ in range(t):
n = int(next(it))
m = int(next(it))
k = int(next(it))
edges = []
for _ in range(m):
edges.append((int(next(it)), int(next(it))))
ans.append(str(solve_case(n, m, k, edges)))
return "\n".join(ans)
assert run("""1
3 3 3
1 2
2 3
1 3
""") == "6"
assert run("""1
3 0 2
""") == "8"
assert run("""1
3 3 2
1 2
2 3
1 3
""") == "0"
assert run("""1
1 0 5
""") == "5"
assert run("""1
4 6 4
1 2
1 3
1 4
2 3
2 4
3 4
""") == "24"
| Test input | Expected output | What it validates |
|---|---|---|
| Triangle with three colors | 6 | Complete graph color permutations |
| Empty graph | 8 | Independent choices without edges |
| Triangle with two colors | 0 | Impossible coloring detection |
| Single vertex | 5 | Minimum graph boundary |
| Complete graph with four vertices | 24 | Large branching and color constraints |
Edge Cases
For an empty graph such as:
1
3 0 2
the search never marks any color as forbidden. Every recursive branch survives until all vertices are assigned, producing 2^3 = 8.
For a complete graph with fewer colors:
1
3 3 2
1 2
2 3
1 3
the first two vertices can receive different colors, but the third vertex has both colors forbidden. That branch ends immediately, and every other branch fails in the same way, producing zero.
For a single vertex:
1
1 0 5
the recursion chooses the only vertex and tries five possible colors. Each one creates a complete coloring, so the answer is five. This also verifies that the termination condition works when the graph contains no edges and no recursive depth is needed.