自动搬运

查看原文

来自洛谷，原作者为

	Farkas_W 醉后不知天在水，满船清梦压星河。

搬运于2025-08-24 22:15:11，当前版本为作者最后更新于2020-10-27 21:02:14，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

$\quad$与其它并查集不同，在棋盘上需要二维并查集，用一维数组f记录每个坐标的祖先，用二维数组记录每个点的颜色。（1表示白点，2表示黑点）

$\quad$二维并查集一般采用压缩成一维的方法，将坐标为$(x,y)$的点记录为 $(x-1)\times m+y$ ，$m$ 为一行中点的数量（此题中为 $n$，棋盘是 $n\times n$ 的），这样就可以存储祖先了。

$\quad$由于我从 $1$~$n$ 存储点，数组开的略大，所以没有判断边界，然后新加一个点 $ans$++，连通块合并时 $ans$ - - 即可。

$\quad$使用并查集一定要初始化，最好也要路径压缩(没试过，不知道会不会T)，每次修改直接将一个连通块的祖先并到另一个祖先。(就是敲一个并查集板子)

下面贴上蒟蒻的代码，如果有思路的建议不要看下面的代码，自行思考

#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）。

都看到这了，还不点个赞支持一下!

完结撒花!