色数（Chromatic Number）题解

首先由于每种颜色的点都已一个独立集，所以题目询问的是最少可以将点分为多少个独立集。

注意到 $N\le 20$，考虑状态压缩dp。

设 $dp_s$ 表示将集合 $s$ 分成独立集的最少个数，先将独立集初始化为 $1$，然后枚举子集计算即可。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,p[22];
int dp[1<<21];
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>m;
	for(int i=1,x,y;i<=m;i++){
		cin>>x>>y;x++;y++;
		p[x]|=1<<y-1;p[y]|=1<<x-1;
	}
	for(int s=0;s<(1<<n);s++)dp[s]=114514;//初始化 
	dp[0]=1;//0本身就是独立集 
	for(int s=0;s<(1<<n);s++)if(dp[s]==1){//集合s是独立集 
		for(int i=1;i<=n;i++){
			if(!(p[i]&s)){//s中的点和i不相邻 
				dp[s|(1<<i-1)]=1;
			}
		}
	}
	for(int s=0;s<(1<<n);s++){
		for(int t=s;t;t=(t-1)&s){//枚举子集 
			dp[s]=min(dp[s],dp[t]+dp[s^t]);
		} 
	}
	cout<<dp[(1<<n)-1];
	return 0;
}