集合DP方法用于解决图着色问题（高效枚举）

题目

对于一个无向图G，在其中对所有节点进行着色为最少数量的颜色，并确保任意两个相邻节点颜色不相同。

思路

1. 状态量定义为d(S),其中S表示一个结点集,对该集合进行染色所需颜色数量的最小值。
2. 边界条件设定为d(0)=0。
3. 问题的答案即为d(S)的取值。
4. 状态转移方程如下所示：

\begin{cases} \text{当}~S=\varnothing~\text{时}, & d(S)=0 \\ \text{当}~S\neq\varnothing~\text{时}, & d(S) = \min_{v \in S}\left\{\max_{u \in N(v)} d(\{u\}) + 1\right\} \end{cases}

（内部无边：不存在S`内的两个结点u和v使得u和v相邻）

本题需要枚举子集，所以需要一种高效率枚举子集的方法，如下：

    for (int S0 = S; S0; S0 = (S0 - 1)&S)
    
    AI写代码cpp

关于时间复杂度的分析部分中提到LRJ阐述了许多内容，在后续涉及了较多的数学理论，在当前阶段暂时难以理解这些细节内容：仅需了解枚举所有可能子集的空间复杂度为3^n即可

![这里写图片描述](https://cdl.ita