问题

给出一个个点的连通图,用至多种颜色对图上每个点进行染色，要求任意两个有边直接相连的点不可以同色，染色方案数有多少种，输出方案数，若不存在这样的染色方案输出

解析

本题可以使用分支限界的方法来计算，尝试对每个点进行染***r>剪枝的情况：

  • 1.如果当前尝试染色的点已经有颜色，则不需要继续枚举
  • 2.如果当前尝试染色的点周围已经有相同的颜色，则不需要继续枚举

采用深度优先搜索+回溯的方法来

设计

未染色点个数=n

dfs（当前点，尝试染的颜色）：
遍历所有与当前点相连的点
    如果存在同色的点，则直接退出
给当前点染色，未染色点个数-1
如果未染色点个数=0
    染色方案+1
    退出
枚举所有可能的染色
    枚举所有与当前点相邻的点
        如果这个点没有被染色
            尝试给这个点染色：dfs（新点，新的尝试颜色）

分析

以四个点两种颜色为例
图片说明
分治限界算法的上界为解空间内决策树上最大的点的个数
考虑到每次枚举一个新颜色可能会需要对每个点枚举每种颜色，所以枚举一个点的复杂度上界是，枚举个点总共需要

源码

传送门