洛谷P5877棋盘游戏[NOI导刊]
920+
作者：crxis 发布：2021-05-18 分类：并查集
题目大意：在一个5*9的棋盘下黑子和白子，这个游戏过程中，各个时刻棋盘上有多少个连通块呢？连通块是指颜色相同的相邻的棋子。
题目描述
为了增强幼儿园小朋友的数数能力，小虎老师给了一个家庭游戏作业。让小虎那一块空的围棋盘，随机在一些方格中放些棋子（有黑白两种颜色），如果一个方格和它的上、下、左、右四个方格之一有相同颜色的棋子，则认为两个格子是相互连通的。这期间，要求小虎不断统计共有多少个连通块。
如下图是一个 $5\times 9$ 的一块棋盘，其中 `.` 表示空格，`*` 表示黑棋子，`@`表示白棋子。
则有 $4$ 块连通子块。
“`
. . . . . . . . .
. . * * . . @ @ .
. * * @ @ . @ @ .
. . * @ . . * . .
. . . . . . . . .
“`
哥哥大虎在一边看一边想，如果棋盘是 $N\times N$ 的，共放了 $M$ 个棋子，如何使用计算机解决这个问题呢？
输入输出格式
输入格式
第一行两个整数：$N,M$。
接下来有 $M$ 行，每行三个整数：$c, x, y$。分别表示依次放入棋子的颜色（ $0$ 表示白色，$1$ 表示黑色）、要放入格子的横坐标和格子的纵坐标。
输出格式
共 $M$ 行。第 $i$ 行一个整数，表示放入第 $i$ 个棋子后，当前有多少个棋子连通块。
输入输出样例
输入样例 #1
3 5
1 1 1
1 1 2
0 2 2
1 3 1
1 2 1
输出样例 #1
1
1
2
3
2
输入样例 #2
3 5
1 1 2
1 2 1
1 3 2
1 2 3
1 2 2
输出样例 #2
1
2
3
4
1
说明
对于 $30\%$ 数据：$1\le N \le 10$。
对于 $60\%$ 数据：$1\le N\le 100$。
对于 $100\%$ 数据：$1\le N\le 500$，$1\le M \le N \times N$，$ 0 \le c \le 1$，$ 1\le x, y \le N$。
解题思路
考察并查集。每下一个棋子，就增加一个连通块；如果这个棋子周围，有同色的棋子块，则合并，减少一块。
程序实现
