奇妙的模型转化以及并查集思想
模型概述
有图$G=(V,E)$，初始所有点为白色，现在要将其中一些点染为黑色，要求染色后满足：$∀(u,v)∈E$，$∃col_u!=col_v$。求最小染色点数。
题目描述
曹是一只爱刷街的老曹，暑假期间，他每天都欢快地在阳光大学的校园里刷街。河蟹看到欢快的曹，感到不爽。河蟹决定*阳光大学，不让曹刷街。
阳光大学的校园是一张由N个点构成的无向图，N个点之间由M条道路连接。每只河蟹可以对一个点进行*，当某个点被*后，与这个点相连的道路就被*了，曹就无法在与这些道路上刷街了。非常悲剧的一点是，河蟹是一种不和谐的生物，当两只河蟹*了相邻的两个点时，他们会发生冲突。
询问：最少需要多少只河蟹，可以*所有道路并且不发生冲突。
输入输出格式
输入格式：
第一行：两个整数N，M
接下来M行：每行两个整数A，B，表示点A到点B之间有道路相连。
输出格式：
仅一行：如果河蟹无法*所有道路，则输出“Impossible”，否则输出一个整数，表示最少需要多少只河蟹。
说明
【数据规模】
1<=N<=10000，1<=M<=100000，任意两点之间最多有一条道路。
题目分析
本来想写道图论题的，但看题解时候看到一篇并查集的题解感觉非常奇妙……
常规做法
大力搜索？黑白染色？好像无向图缩环之类的在这道题没什么用。
dp也无能为力，因为虽说和树形dp那里独立集全覆盖有些相像，但是这题是图的形式，有环的约束，也不能简单地缩点。
奇妙的并查集
观察一下要求：
- 所有道路都要求被覆盖
- 选取满足要求的独立集
诶，那么就是说“敌人的敌人就是我的朋友”咯？
这不就成了[BOI2003]团伙那道题吗？
回顾一下那题，我们可以用$enemy[x]$表示所有$x$的敌人。这种思想可以快速合并不在一个集合内的元素，而且非常巧妙！
姑且就称为补集转化的思想吧。这里是以前写的团伙的博客。
（感觉好像有那么一点像2-sat？？？）
#include<bits/stdc++.h>
const int maxn = ; int sum[maxn],fa[maxn],enemy[maxn];
int n,m,ans;
bool vis[maxn]; int get(int x){return fa[x]==x?x:fa[x]=get(fa[x]);}
void unions(int x, int y)
{
int fx = get(x), fy = get(y);
fa[fx] = fy, sum[fy] += sum[fx], sum[fx] = ;
}
int main()
{
scanf("%d%d",&n,&m);
for (int i=; i<=n; i++) fa[i] = i, sum[i] = ;
for (int i=; i<=m; i++)
{
int a,b,fa,fb;
scanf("%d%d",&a,&b);
fa = get(a), fb = get(b);
if (fa!=fb){
if (enemy[a]) unions(enemy[a], fb);
if (enemy[b]) unions(enemy[b], fa);
enemy[a] = fb, enemy[b] = fa;
}
else{
puts("Impossible");
return ;
}
}
for (int i=; i<=n; i++)
{
int x = get(i);
if (!vis[x]){
int y = get(enemy[x]);
ans += std::min(sum[x], sum[y]);
vis[x] = vis[y] = ;
}
}
printf("%d\n",ans);
return ;
}
END