Open Wizmann opened 3 years ago
Problem
给定一个N个点，M条边的无向图。图中不包含重边和自环。
给图中的所有点染成RGB三色之中的一种，使得一条边的两个端点不是同一种颜色。
问有多少种染色方法。
穷举是不能穷举的，20^3铁定超时。
首先考虑染色方法最多的场景，一定是只有点，没有连边。这样染色种数最多。然后我们在这个图中加一条边，就会引入一个限定条件（边的两端点颜色不同）。
再考虑一个连通图中，最多能有多少种染色方法。限制最少的联通图，一定是链状结构，每个点有且仅有两个限定条件（不可能再少了）。简单手算，其最终结果有3 * 2^19 = 1572864种方法。
所以，对于连通的图块，我们可以使用“DFS+剪枝”进行枚举；对于独立的点，直接乘方进行计数即可。
在DFS的实现上，要注意图可能不是连通的。所以需要预处理，根据连能性分割成多个子图，分开计算，实现起来会简单的多。
Code
Description
Problem
给定一个N个点，M条边的无向图。图中不包含重边和自环。
给图中的所有点染成RGB三色之中的一种，使得一条边的两个端点不是同一种颜色。
问有多少种染色方法。
Solution
穷举是不能穷举的，20^3铁定超时。
首先考虑染色方法最多的场景，一定是只有点，没有连边。这样染色种数最多。然后我们在这个图中加一条边，就会引入一个限定条件（边的两端点颜色不同）。
再考虑一个连通图中，最多能有多少种染色方法。限制最少的联通图，一定是链状结构，每个点有且仅有两个限定条件（不可能再少了）。简单手算，其最终结果有3 * 2^19 = 1572864种方法。
所以，对于连通的图块，我们可以使用“DFS+剪枝”进行枚举；对于独立的点，直接乘方进行计数即可。
在DFS的实现上，要注意图可能不是连通的。所以需要预处理，根据连能性分割成多个子图，分开计算，实现起来会简单的多。
Code