SSL_2415 连通块

本文主要是介绍SSL_2415 连通块，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意

给出一个$n \times n$的矩阵，有m次操作，可以在第(x,y)格放上颜色为z的方块，与它上左下右相连的方块与它是同一块，求每次操作时，在这个矩阵里共有多少块方块（颜色0代表白，1代表黑）。

思路

每次插入时先让答案+1，利用并查集，判断与这个方块相连的方块是否和它为同一个集合，如果为同一个集合我们就让它们合并并且让答案-1，如果它们已经为同一个集合我们就不用让答案-1了，防止掉坑。

代码

#include<cstdio>
int n,m,f,ans,father[250010],map[501][501];
short dx[5]={0,0,0,1,-1},dy[5]={0,1,-1,0,0};
int find(int x)
{return x==father[x]?x:find(father[x]);
}
void unio(int x,int y) 
{x=find(x);y=find(y);if (x==y) return;//如果已经同一个集合了就不让ans-了if (x>y) father[x]=y;else father[y]=x;ans--;
}
int main()
{scanf("%d%d",&n,&m);int x,y,z;for (int i=1;i<=n*n;i++) father[i]=i;for (int i=1;i<=m;i++){ans++;scanf("%d%d%d",&z,&x,&y);z++;//因为颜色一开始都初始化为0，所以要让z++map[x][y]=z;//map记录这些方块for (int j=1;j<=4;j++){if (x+dx[j]>0&&x+dx[j]<=n&&y+dy[j]>0&&y+dy[j]<=n//如果满足范围&&map[x+dx[j]][y+dy[j]]==z)//相连的方块颜色相同 unio((x-1)*n+y,(x+dx[j]-1)*n+y+dy[j]);//判断并合并}printf("%d\n",ans);}
}

这篇关于SSL_2415 连通块的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---