并查集的刷题
皎月半洒花
2018-03-06 11:46:41
说实话，这几天被并查集日到生无可恋$qnq$
ε=(´ο｀*)))唉……就类似于你被一个很古老的算法抽了一瓜子之后发现很多题都可以用这个算法解决但是——你不会$qnq$
先来看第一个例题吧！
[简单难度qwq](https://www.luogu.org/problemnew/show/P1892)
这个题很显然啊，**它的一半**就是一个裸的不能再裸的并查集了。就是关于朋友的朋友那个$qwq$。而另外一部分，则是“敌人的敌人是朋友”，这就比较有意思了——怎么把两个自己的敌人的合并呢？最后又该怎么统计到底有几个团伙呢？然后，脑袋乱作一团$qnq$。
### 而这时，我们唯一需要的，就是冷静。因为并查集类型的题目，难点就是在于如何判断关系和如何合并上，所以需要冷静地理清关系。
那么我们可以看：合并自己的两个敌人，无非就是相当于合并两个没有确立朋友关系的陌生人。那么在合并时唯一需要注意的就是如何合并。再看，如何合并呢？我们可以考虑一个已经出现在一组敌人关系里的$x$号,在这时又出现了一个关于$x$号的敌人关系，那此时我们只需要把这两次$x$的敌人合并就好。也就是说，我们完全可以通过**记录**每个点的敌人编号，来实现合并操作。
嗯就是这样，还有别忘了一开始一定要有$f[i]=i$呀！
------------
```cpp
#include<iostream>
#include<cstring>
using namespace std;
int enemy[10001],father[10001];
bool record[10001];
struct rela{
int f,t;
}r[100001];
int find(int a)
{
if(a!=father[a])a=find(father[a]);
return a;
}
void unionn(int a,int b)
{
if(father[a]!=father[b])
father[find(a)]=father[find(b)];
}
int main()
{
int n,m;
char a;
cin>>n>>m;
for(register int i=1;i<=n;i++)
{
father[i]=i;
}
for(register int i=1;i<=m;i++)
{
cin>>a;
cin>>r[i].f>>r[i].t;
if(a=='F')unionn(r[i].f,r[i].t);
if(a=='E')
{
if(enemy[r[i].f]==0)enemy[r[i].f]=r[i].t;
else
unionn(r[i].t,enemy[r[i].f]);
if(enemy[r[i].t]==0)enemy[r[i].t]=r[i].f;
else
unionn(r[i].f,enemy[r[i].t]);
}
}
memset(record,0,sizeof(record));
int sum=0;
for(register int i=1;i<=n;i++)
{
record[find(i)]=1;//笨拙地记录qwq
}
for(register int i=1;i<=n;i++)
{
if(record[i]==1)sum++;//笨拙地查找qwq*2
}
cout<<sum;
}
```
------------------------------
好的惹，再来看第二个$qwq$
[中等难度](https://www.luogu.org/problemnew/show/P1525)
居然有大佬用二分图染色做！$ORZ$我二分图还不会呢！！
其实这个题，也可以形象地用“加权并查集”来形容。因为可以看出来，它的每一组关系都有一个权值。而我们可以考虑两个不同的贪心——每次把当前最小的一组关系合并，和每次把当前最大的一组关系分开。乍一看上去，好像都是一样的。但其实，第一种贪心是不对的，因为如果我们每次都把最小的一组关系合并，我们就不能确定我们当前合并的几个元素里面是否有一组我们从小到大还未枚举到的、恶劣指数更高的关系，所以错。而如果从大到小分开，那么一定不会有更恶劣的关系在同一个监狱里，所以正确。
那么好了，若我们从大到小枚举，该怎么分开呢？很简单，还是记录，不过记录的是 一定 和每个已经枚举过的 关系中 包含的 人（记为$x$） 不在 同一个监狱 的人(记为$y$)。（有点长，划分了节奏$qvq$）
然后，如果以后再碰到和一组关系中包含$x$,那我们就把这组关系中的另一个人和$y$合并——**因为我们的贪心决定，在此之前未曾枚举过的关系，恶劣程度一定较小。**
So,贴标程
_____________
```cpp
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
struct rela{
int x,y,z;
}f[100005];
int n,m,a[20005],b[20005],i;
inline bool cmp(rela a,rela b)
{
return a.z>b.z;
}
inline int find(int x)
{
if(a[x]!=x) x=find(a[x]);
return x;
}
inline void ad(int x,int y)
{
a[find(x)]=a[find(y)];
}
int main()
{
cin>>n>>m;
for(i=1;i<=n;i++)a[i]=i;
for(i=1;i<=m;i++)
scanf("%d%d%d",&f[i].x,&f[i].y,&f[i].z);
sort(f+1,f+m+1,cmp);
for(i=1;i<=m+1;i++)
{
if(find(f[i].x)==find(f[i].y))
{
printf("%d",f[i].z);
return 0;
}
else
{
if(!b[f[i].x]) b[f[i].x]=f[i].y;
else {ad(b[f[i].x],f[i].y);}
if(!b[f[i].y]) b[f[i].y]=f[i].x;
else {ad(b[f[i].y],f[i].x);}
}
}
}
```
哦，对，还有一个小优化，由于最后还要特判$0$，所以可以直接多加一次循环，用来输出$0$
_________________________________________
那么看第三个例题吧，其实第三个例题从思维量上好像没有第二个那么大，但是他用并查集用的巧妙啊——其实也不是多巧妙，只不过现代年轻人（比如我）不够灵活，太死板了而已。
看题吧$qwq$
[中等难度](https://www.luogu.org/problemnew/show/P2024#sub)
其实这个题就是让我们利用前两个条件来判断前面的关系是否满足，然后用第三个条件来判断之后得到几组关系是否满足。
还是那句话，先冷静分析问题、剖析关系。
·首先，两个生物是同类的条件是，他们不是食物关系。
·其次，两个生物满足$A$吃$B$的条件是，他们不是同类，并且不是相反的食物关系（比如$B$吃$A$）
好像……是废话?没什么用？其实不然，它给我们提供了一种思路：用三个并查集，来记录三个不同的角色：$A$、$B$、$C$
诶？那岂不是要写三个不同的$find$和三个不同的$union$函数？？
$emmmmm$其实这么做也可以，不过有点麻烦而已。我们只需要用一个数组，它的$1$~$n$表示$A$，$n+1$~$2\times{n}$表示B，$2\times{n}+1$~$3\times{n}$表示C就好。
这个故事告诉我们，要灵活啊！！！
**哦，还有，我们在遇到一组正确的“同类关系”之后，就要合并他们的天敌和食物；在遇到一组正确的食物关系后，就要错位合并他们的引申关系**
```cpp
#include<cstdio>
#include<iostream>
int f[300011];
int n,k,sum;
inline int find(int x)
{
if(x!=f[x]) x=find(f[x]);
return x;
}
inline int unionn(int x,int y)
{
int r1=find(f[x]),r2=find(f[y]);
f[r1]=r2;
}
int main()
{
int x,y,z;
std::cin>>n>>k;
for(register int i=1;i<=3*n;++i) f[i]=i;
for(register int i=1;i<=k;++i)
{
scanf("%d%d%d",&z,&x,&y);
if(x>n||y>n)
{
sum++;
continue;
}
switch(z)
{
case 1:
{
if(find(x+n)==find(y)||find(x+2*n)==find(y))
{
sum++;
continue;
}
unionn(x,y); unionn(x+n,y+n); unionn(x+2*n,y+2*n);
break;
}
case 2:
{
if(x==y) {sum++; continue;}
if(find(x)==find(y)||find(x+2*n)==find(y))
{
sum++;
continue;
}
unionn(x,y+2*n); unionn(x+n,y); unionn(x+2*n,y+n);
break;
}
}
}
printf("%d\n",sum);
return 0;
}
```
//4.28更新
实际上因该昨天更新的……但是由于昨天想更新的时候被查水表了，所以只能今天更新了ORZ
这个题……略微偏难一些吧，大约[中等偏难](https://www.luogu.org/problemnew/show/P1197)的样子。
三个字，离线存储摧毁的星球，然后倒着加边，得出结果后再正着输出，Over.
## $\color{red}Code$
```cpp
// luogu-judger-enable-o2
#include<iostream>
#include<cstdio>
using namespace std;
#define MAXM 400001
struct edge{
int to,next;
}e[MAXM];
int head[MAXM<<1],ans[MAXM],f[MAXM<<1],cnt,edge[MAXM][2],GG[MAXM];
bool broken[MAXM<<1];
inline void add(int u,int v){
cnt++;
e[cnt].to=v;
e[cnt].next=head[u];
head[u]=cnt;
}
int find(int x){
if(x==f[x])return x;
return f[x]=find(f[x]);
}
inline void unionn(int a,int b){
f[find(a)]=f[find(b)];
}
int main(){
int n,m,a,b;
cin>>n>>m;
for(int i=0;i<=n-1;i++){
f[i]=i;
}
for(int i=1;i<=m;i++){
cin>>a>>b;
add(a,b);
add(b,a);
edge[i][0]=a;
edge[i][1]=b;
}
int k;cin>>k;
for(int i=1;i<=k;i++){
cin>>a;
broken[a]=true;
GG[i]=a;
}
for(int i=1;i<=m;i++){
if(find(edge[i][0])!=find(edge[i][1])&&!broken[edge[i][0]]&&!broken[edge[i][1]]){
unionn(edge[i][0],edge[i][1]);
}
}
int tot=0;
for(int i=0;i<n;i++){
if(f[i]==i&&!broken[i])tot++;
}
for(int i=k;i>=1;i--){
ans[i]=tot;
for(int j=head[GG[i]];j;j=e[j].next){
if(find(e[j].to)!=find(GG[i])&&!broken[e[j].to]){
tot--;
unionn(e[j].to,GG[i]);
}
}
tot++;
broken[GG[i]]=0;
}
ans[0]=tot;
for(int i=0;i<=k;i++){
cout<<ans[i]<<endl;
}
}
```