题意：
给出n个点，m条边，将若干个点染色，使得每个边至少有一点染色，问至少染多少个点。
思路：
如果是二分图，那就是最小点覆盖，但是这是一般图。
一般图的最小覆盖是npc问题，但是这题有一个条件比较特殊，就是输入的每条边都保证了至少有一个点小于等于30，所以至多覆盖30个点就可以了。
那么就可以用搜索解决，对于一个点，要么覆盖，要么不覆盖。
如果这个点被覆盖了，就直接往下搜；
如果没有被覆盖，那么就要么覆盖这个点，直接往下搜；要么不覆盖这个点，但把这个点相邻的点全部覆盖，再往下搜。
得剪枝，可行性剪枝和最优性剪枝。
代码：
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
using namespace std;
const int N = ;
int vis[N];
vector<int> g[N];
int tot;
int ans;
void dfs(int cu,int sum)
{
if (sum > ans) return;
if (cu > tot)
{
ans = sum;
return;
}
if (vis[cu]) dfs(cu+,sum);
else
{
vis[cu]++;
dfs(cu+,sum+);
vis[cu]--;
for (auto x : g[cu])
{
if (!vis[x]) sum++;
vis[x]++;
}
dfs(cu+,sum);
for (auto x : g[cu])
{
vis[x]--;
if (!vis[x]) sum--;
}
}
}
int main()
{
int n,m;
while (scanf("%d%d",&n,&m) != EOF)
{
tot = ;
ans = ;
memset(vis,,sizeof(vis));
for (int i = ;i <= n;i++) g[i].clear();
for (int i = ;i < m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
g[x].push_back(y);
g[y].push_back(x);
}
tot = min(,n);
ans = tot;
dfs(,);
printf("%d\n",ans);
}
return ;
}