题目描述

塔子哥有一个无向图，图中有若干个节点是红色，其余为白色。塔子哥想知道，将$i$染成红色，当前图中红色连通块的数量是多少？

输入描述

思路：并查集

给定一个无向图，有些节点是白色，有些节点是红色。求将第$i$个节点染红后，有多少个红色连通块。

红色节点染红，显然红色连通块的数目不变。

将白色节点染红，则要取决于与该染红节点相邻的节点有多少已经是红色的。而这些已经是红色的节点有可能已经位于同一个连通块中了，因此我们需要使用并查集来判断它们是否处于同一个集合。

最开始，通过某一个未被标记的红色节点开始遍历，将其所能到达的所有红色节点划分到该集合中，然后标记。重复上述过程，直到所有红色节点都被划分进集合中。此时可以求到集合总数为$res$，也就是最开始的答案或者说将红色节点染红的答案。