题解 P5877 【棋盘游戏】
Farkas_W
·
·
题解
\text{求连通块数量，首先想到二维并查集}
$\quad$二维并查集一般采用压缩成一维的方法，将坐标为$(x,y)$的点记录为 $(x-1)\times m+y$ ，$m$ 为一行中点的数量（此题中为 $n$，棋盘是 $n\times n$ 的），这样就可以存储祖先了。
$\quad$由于我从 $1$~$n$ 存储点，数组开的略大，所以没有判断边界，然后新加一个点 $ans$++，连通块合并时 $ans$ - - 即可。
$\quad$使用并查集一定要初始化，最好也要路径压缩(没试过，不知道会不会T)，每次修改直接将一个连通块的祖先并到另一个祖先。(就是敲一个并查集板子)
下面贴上蒟蒻的代码，如果有思路的建议不要看下面的代码，自行思考
```cpp
#include<iostream>
#include<cstdio>
#define il inline
#define re register int
using namespace std;
il int read() //快速读入
{
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)&&ch!='-')ch=getchar();
if(ch=='-')f=-1,ch=getchar();
while(isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
return x*f;
}
il void print(int x)//快速输出
{
if(x<0)putchar('-'),x=-x;
if(x/10)print(x/10);
putchar(x%10+'0');
}
const int N=505;
int n,m,a[N][N],ans,f[N*N]; //ans记录连通块数量
int fx[5]={0,1,-1,0,0},fy[5]={0,0,0,1,-1};//用数组存储位置变化，方便判断
il int find(int x) //并查集 路径压缩
{
if(x!=f[x])f[x]=find(f[x]);
return f[x];
}
signed main()
{
n=read();m=read();
for(re i=1;i<=n*n;i++)f[i]=i;//并查集初始化
for(re i=1;i<=m;i++)
{
int z=read()+1,x=read(),y=read();//因为a数组初始化为0，所以read()+1，用1表示白点，用2表示黑点,与0区分
a[x][y]=z; //标记颜色
ans++; //增加连通块数量
for(re j=1;j<=4;j++) //向上下左右四个方向判断是否连通
{
int xx=x+fx[j],yy=y+fy[j];
if(a[xx][yy]!=z)continue; //条件1：颜色相同
int fa=find((xx-1)*n+yy),fu=find((x-1)*n+y);
if(fa!=fu)f[fa]=fu,ans--; //条件2：祖先不同 ——>合并祖先，连通块数量减少
}
print(ans);putchar('\n'); //输出
}
return 0;
}
```
$\large\text{后话}
本蒟蒻目前速度最快（不开O2）。
都看到这了，还不点个赞支持一下!
完结撒花!