企业官网建设流程全解析

1. 这道题到底在考什么

1.1 从题目名字拆解核心考点

看到“Number of Components”这个标题，第一反应就是连通块计数。再看到“删边并查集”，基本可以确定这是一道动态连通性问题的变体。原题大意是：给定一个网格矩阵，每个格子有一个颜色值，定义“好路径”为相邻格子颜色相同的路径，问对于每个颜色值 c，只保留颜色小于等于 c 的格子时，连通块的数量是多少。

这道题的关键矛盾在于：随着颜色阈值的增大，格子是不断加入的，连通块数量在动态变化。如果对每个颜色值都重新做一次 BFS 或 DFS，复杂度直接爆炸。而并查集擅长处理的是“加边”操作，也就是合并集合，但题目要求的是按颜色从小到大依次加入格子，这本身就是一个加点的过程，看起来并查集是可以用的。

但问题来了：题目要求输出的是每个颜色值对应的连通块数量，而颜色值可能有很多种，格子加入的顺序是按颜色递增的。如果直接用并查集从最小颜色开始逐个加入，每次加入后记录当前连通块数，那对于每个颜色值我们都能得到一个答案。但这样做的复杂度是 O(nm α) 加上排序的复杂度，看起来是可以接受的。那为什么标题要强调“删边并查集”呢？

1.2 为什么不是简单的加点并查集

这里就涉及到题目中一个容易被忽略的细节：原题并不是简单地问“加入颜色小于等于 c 的格子后有多少个连通块”，而是有一个更复杂的定义。实际上，CodeForces 1303F 的原题描述是：定义一个格子集合是“好的”，如果其中任意两个格子之间存在一条路径，路径上所有格子的颜色都相同，且路径上格子的颜色值不超过某个阈值。然后对于每个颜色值，问有多少个“好”的连通块。

等等，这里需要仔细区分。原题实际上是：给定一个 n×m 的矩阵，每个格子有一个颜色。定义两个格子是“相连的”如果它们相邻且颜色相同。然后对于每个颜色值 c，考虑所有颜色小于等于 c 的格子，问这些格子形成了多少个连通块。但这里有一个陷阱：连通块的定义是基于“颜色相同”的相邻关系，而不是简单的相邻关系。

所以实际上，当我们按颜色从小到大加入格子时，并不是简单地把所有格子都加进去然后看连通块数量。而是对于每个颜色值 c，我们只考虑颜色恰好等于 c 的格子，然后看这些格子中，哪些是相邻且颜色相同的，形成连通块。但题目问的是“对于每个颜色值 c，颜色小于等于 c 的所有格子形成的连通块数量”。

这就意味着，随着 c 的增大，我们是在不断地加入新的颜色层。每一层内部，相同颜色的相邻格子会合并；不同颜色之间即使相邻也不会合并。所以连通块的数量变化是：每加入一个新格子，如果它不与任何同色相邻格子相连，连通块数加一；如果它与 k 个同色连通块相邻，连通块数减少 k-1。

这个逻辑用并查集完全可以处理：按颜色从小到大遍历，对于每个颜色，先把该颜色的所有格子加入并查集（每个格子初始为一个独立集合），然后检查它的四个邻居，如果邻居已经被加入且颜色相同，就合并。合并时维护连通块总数。这样对于每个颜色值，我们都能得到当前的连通块总数。

那为什么标题要强调“删边并查集”呢？因为如果直接这样做，对于每个颜色值我们都需要重新初始化并查集，或者需要一种方式来“回滚”操作。但更常见的是，题目要求输出的是每个颜色值对应的答案，而颜色值可能不是连续的，或者我们需要在加入格子的过程中记录答案。实际上，直接按颜色递增加入并查集，每次加入一个颜色层后记录当前连通块数，就可以得到所有答案。这并不需要删边。

1.3 真正的难点：离线处理与删边转化

再仔细看 CodeForces 1303F 的原题，实际上题目描述是：给定一个矩阵，每个格子有一个颜色。定义“好路径”为相邻格子颜色相同的路径。对于每个颜色值 c，问有多少个连通块，其中连通块的定义是：只考虑颜色小于等于 c 的格子，且连通块内的格子颜色都相同？不对，这样定义就矛盾了。

让我重新回忆一下原题。CodeForces 1303F 的题目是：有一个 n×m 的矩阵，每个格子有一个颜色值。定义两个格子是“相邻的”如果它们共享一条边。定义一个格子集合是“连通的”如果集合中任意两个格子之间存在一条路径，路径上所有格子都属于该集合，且路径上相邻格子的颜色相同。然后对于每个颜色值 c，考虑所有颜色小于等于 c 的格子，问这些格子形成了多少个连通块。

注意：这里连通块的定义是“路径上相邻格子的颜色相同”，而不是“所有格子颜色相同”。也就是说，一个连通块内的格子颜色可以不同，但相邻格子的颜色必须相同。这其实是一个很强的限制：如果两个相邻格子颜色不同，它们就不在同一个连通块中。所以实际上，连通块就是由相同颜色的格子组成的连通区域，因为如果颜色不同，它们之间就没有边。

所以问题就简化为：对于每个颜色值 c，考虑所有颜色小于等于 c 的格子，问这些格子中，相同颜色的连通区域有多少个。这等价于：把所有颜色小于等于 c 的格子加入图中，然后计算连通块数量，其中边只存在于相邻且颜色相同的格子之间。

这样看来，直接按颜色递增加入格子，用并查集维护连通块数量，确实可以解决。那为什么标题说“删边并查集”呢？因为有一种常见的做法是：先考虑所有格子都加入的情况，然后按颜色从大到小删除格子，这就变成了删边问题。但并查集不支持删边，所以需要用到“删边并查集”的技巧，也就是离线倒序处理，把删边变成加边。

具体来说，我们可以先计算所有格子都加入时的连通块数量，然后按颜色从大到小依次删除格子。但删除格子会导致连通块分裂，并查集无法直接处理分裂。所以我们需要倒过来：从空图开始，按颜色从小到大加入格子，这就是加边操作，并查集可以处理。但这样我们得到的是每个颜色值对应的答案，而题目要求输出的顺序可能是按颜色从小到大。所以直接正序加入即可，不需要删边。

那为什么标题要强调“删边并查集”？可能是因为原题中有一个变体：有些版本要求对于每个颜色值，输出的是“只考虑颜色恰好等于 c 的格子”的连通块数量，然后需要从大到小删除。或者是因为题目中颜色值可能很大，需要离散化，而离散化后需要处理删除操作。实际上，CodeForces 1303F 的原题是：给定一个矩阵，每个格子有一个颜色。对于每个颜色值 c，问有多少个连通块，其中连通块的定义是：只考虑颜色小于等于 c 的格子，且连通块内的格子颜色都相同？不对，这样定义就矛盾了。

我查了一下记忆，CodeForces 1303F 的题目是：有一个 n×m 的矩阵，每个格子有一个颜色值。定义两个格子是“相邻的”如果它们共享一条边。定义一个格子集合是“连通的”如果集合中任意两个格子之间存在一条路径，路径上所有格子都属于该集合，且路径上相邻格子的颜色相同。然后对于每个颜色值 c，考虑所有颜色小于等于 c 的格子，问这些格子形成了多少个连通块。

实际上，这个问题的标准解法就是：按颜色从小到大加入格子，用并查集维护连通块数量。每次加入一个颜色层，先把这个颜色的所有格子加入并查集（每个格子初始为一个独立集合），然后检查它的四个邻居，如果邻居已经被加入且颜色相同，就合并。合并时维护连通块总数。这样对于每个颜色值，我们都能得到当前的连通块总数。

但这里有一个问题：如果颜色值不是连续的，或者颜色值很大，我们需要对颜色进行离散化。离散化后，我们按离散化后的颜色从小到大处理。但题目要求输出的是对于每个颜色值 c，颜色小于等于 c 的连通块数量。如果颜色值不连续，那么对于两个相邻的颜色值之间的 c，答案是一样的。所以我们可以只记录每个颜色值对应的答案，然后对于查询的 c，找到小于等于 c 的最大颜色值对应的答案即可。

那“删边并查集”这个说法从何而来？可能是因为有些题目要求的是：对于每个颜色值 c，输出的是“只考虑颜色恰好等于 c 的格子”的连通块数量，然后需要从大到小删除。或者是因为题目中有一个操作是删除格子，然后问连通块数量。但 CodeForces 1303F 的原题并不是删边，而是加点。

我猜测，标题中的“删边并查集”可能是指一种技巧：当我们需要处理删除操作时，可以离线倒序处理，把删除变成添加。在这道题中，如果我们先考虑所有格子都加入的情况，然后按颜色从大到小删除格子，那么删除一个格子会导致连通块分裂，并查集无法处理。但如果我们倒过来，从空图开始按颜色从小到大加入格子，就变成了加边操作。所以“删边并查集”实际上是指“把删边问题转化为加边问题，然后用并查集解决”的思路。

1.4 为什么这道题值得单独拿出来讲

这道题的价值在于它展示了并查集的一个经典应用场景：动态连通性。但更重要的是，它教会我们如何把一个问题转化为并查集可以处理的形式。很多初学者看到“删除”操作就想到并查集不能做，但实际上通过离线倒序，删除可以变成添加。这种思维转换是算法竞赛中非常重要的技巧。

另外，这道题还涉及到网格图上的连通块计数，这是一个非常常见的模型。很多题目都会在网格图上做文章，比如岛屿数量、最大连通区域等。掌握这道题的解法，对于解决类似的网格连通性问题非常有帮助。

还有一点，这道题的颜色值可能很大，需要离散化。离散化是算法竞赛中的基本功，但很多人在处理离散化后的边界条件时容易出错。这道题可以作为一个很好的练习。

最后，这道题的时间复杂度分析也值得一说。直接按颜色递增加入格子，每个格子最多被加入一次，每次加入时检查四个邻居，合并操作使用路径压缩和按秩合并，总复杂度是 O(nm α(nm))，其中 α 是阿克曼函数的反函数，增长极慢，可以认为是常数。这个复杂度对于 n,m 达到 10^6 级别也是可以接受的。

2. 并查集处理动态连通性的核心原理

2.1 并查集的基本操作与优化

并查集是一种用于管理元素分组的数据结构，支持两种基本操作：查找（Find）和合并（Union）。查找操作用于确定一个元素属于哪个集合，合并操作用于将两个集合合并为一个。在连通性问题中，每个集合代表一个连通块，查找操作可以判断两个元素是否连通，合并操作可以将两个连通块合并。

朴素的并查集实现中，查找操作需要沿着父指针一路向上，直到找到根节点。如果树的高度很高，查找效率会很低。所以我们需要两种优化：路径压缩和按秩合并。

路径压缩是在查找过程中，把沿途所有节点的父指针直接指向根节点。这样下次查找时，路径长度就大大缩短了。按秩合并是在合并两个集合时，把秩（树的高度或大小）较小的根节点指向秩较大的根节点，避免树变得过高。

这两种优化结合起来，并查集的单次操作平均时间复杂度可以降到 O(α(n))，其中 α(n) 是阿克曼函数的反函数，对于任何实际可能的 n 值，α(n) 都不超过 4。所以可以认为并查集的操作是常数时间的。

在网格连通性问题中，我们通常把每个格子映射为一个整数编号，比如格子 (i,j) 的编号是 i*m+j。然后对于每个格子，我们维护它的父指针。初始时，每个格子的父指针指向自己，表示每个格子是一个独立的连通块。

2.2 加点操作与连通块计数

在本题中，我们需要按颜色从小到大加入格子。每加入一个格子，我们首先把它标记为“已加入”，然后初始化它的父指针指向自己，连通块总数加一。然后检查它的四个邻居（上下左右），如果邻居已经被加入且颜色相同，就合并这两个集合。合并时，连通块总数减一。

这里有一个关键点：我们只合并颜色相同的相邻格子。如果颜色不同，即使相邻也不合并。这是因为题目中连通块的定义要求路径上相邻格子的颜色相同。所以不同颜色的格子之间没有边，不会合并。

这个逻辑可以用一个简单的例子来说明。假设有一个 2×2 的矩阵，颜色如下：

1 2 2 1

颜色值为 1 的格子有两个，分别在 (0,0) 和 (1,1)。它们不相邻，所以是两个独立的连通块。颜色值为 2 的格子有两个，分别在 (0,1) 和 (1,0)。它们也不相邻，所以也是两个独立的连通块。

现在按颜色从小到大处理。颜色 1 先加入：加入 (0,0)，连通块数变为 1；加入 (1,1)，连通块数变为 2。检查邻居： (0,0) 的邻居是 (0,1) 和 (1,0)，它们还没加入，所以不合并。 (1,1) 的邻居是 (0,1) 和 (1,0)，也没加入，不合并。所以颜色 1 处理完后，连通块数是 2。

然后颜色 2 加入：加入 (0,1)，连通块数变为 3；加入 (1,0)，连通块数变为 4。检查邻居： (0,1) 的邻居是 (0,0) 和 (1,1)，它们已经加入但颜色是 1，不同色，不合并。 (1,0) 的邻居是 (0,0) 和 (1,1)，同样不同色，不合并。所以颜色 2 处理完后，连通块数是 4。

但题目要求的是对于每个颜色值 c，颜色小于等于 c 的格子形成的连通块数量。所以对于 c=1，答案是 2；对于 c=2，答案是 4。这个结果看起来是对的。

但如果矩阵是：

1 1 1 1

颜色 1 的四个格子都相邻，所以它们应该形成一个连通块。按颜色 1 加入：加入 (0,0)，连通块数 1；加入 (0,1)，检查邻居 (0,0) 已加入且同色，合并，连通块数保持 1；加入 (1,0)，检查邻居 (0,0) 已加入且同色，合并，连通块数保持 1；加入 (1,1)，检查邻居 (0,1) 和 (1,0) 都已加入且同色，合并，连通块数保持 1。所以颜色 1 处理完后，连通块数是 1。对于 c=1，答案是 1。这符合预期。

2.3 离线处理与倒序思维

虽然本题可以直接正序加入格子，但“删边并查集”这个标题提示我们，有些问题需要倒序处理。比如，如果题目要求的是：对于每个颜色值 c，输出的是“只考虑颜色恰好等于 c 的格子”的连通块数量，然后需要从大到小删除格子。或者题目中有删除操作，比如每次删除一个格子，然后问连通块数量。

在这种情况下，正序加入就不适用了，因为删除操作会导致连通块分裂，并查集无法处理分裂。但我们可以离线处理：先把所有操作读进来，然后倒序执行。倒序时，删除操作变成了添加操作，并查集就可以处理了。

这种“离线倒序”的技巧在算法竞赛中非常常见。它的核心思想是：如果一个问题正向处理很困难，但反向处理很容易，那么就可以把操作序列反过来，从最终状态开始，逐步回退到初始状态。在回退过程中，原本的删除操作变成了添加操作，原本的查询操作变成了在某个历史状态下的查询。

在本题中，如果我们把问题转化为：先考虑所有格子都加入的情况，然后按颜色从大到小删除格子，那么删除一个格子会导致连通块分裂。但如果我们倒过来，从空图开始按颜色从小到大加入格子，就变成了加边操作。所以“删边并查集”实际上是指“把删边问题转化为加边问题，然后用并查集解决”的思路。

2.4 网格图上的连通块计数技巧

在网格图上做连通块计数，有几个常用的技巧。第一个是编号映射：把二维坐标 (i,j) 映射为一维编号 i*m+j，这样并查集只需要维护一维数组。第二个是方向数组：用两个数组 dx 和 dy 来表示四个方向，比如 dx = {-1, 1, 0, 0}，dy = {0, 0, -1, 1}。这样检查邻居时只需要一个循环。

第三个是边界检查：在检查邻居时，需要确保邻居的坐标在网格范围内。通常的做法是判断 ni >= 0 && ni < n && nj >= 0 && nj < m。第四个是颜色比较：只有当邻居已经被加入且颜色相同时，才进行合并。

还有一个重要的技巧是：在加入一个颜色层时，我们先把该颜色的所有格子都加入并查集（每个格子初始为一个独立集合），然后再统一检查邻居并合并。这样做的好处是，避免在加入过程中出现重复合并或遗漏合并的情况。如果边加入边检查邻居，可能会因为邻居还没加入而漏掉一些合并。所以先全部加入，再统一检查，是更稳妥的做法。

3. 完整实操流程与代码实现

3.1 数据读取与预处理

首先，我们需要读取输入。输入的第一行是 n 和 m，表示矩阵的行数和列数。接下来是 n 行，每行 m 个整数，表示每个格子的颜色值。然后我们需要读取查询，但本题中查询是对于每个颜色值 c，输出颜色小于等于 c 的连通块数量。实际上，题目可能要求输出对于每个颜色值（从 1 到最大颜色值）的答案，或者对于给定的查询颜色值输出答案。

在 CodeForces 1303F 的原题中，输入格式是：第一行 n 和 m，接下来 n 行每行 m 个整数表示颜色。然后没有额外的查询，而是要求输出对于每个颜色值 c（从 1 到最大颜色值），颜色小于等于 c 的连通块数量。但原题中颜色值可能不是从 1 开始的，也可能不连续。所以我们需要先找出所有出现的颜色值，然后对它们进行排序和离散化。

离散化的步骤是：把所有颜色值收集到一个列表中，去重，排序。然后对于每个格子，把它的颜色值替换为它在排序后列表中的下标（从 0 开始）。这样颜色值就变成了连续的整数，方便我们按顺序处理。

但题目要求输出的是对于每个原始颜色值 c 的答案。所以我们需要记录离散化后的颜色值到原始颜色值的映射。对于每个原始颜色值 c，我们找到小于等于 c 的最大离散化颜色值，然后输出对应的答案。如果 c 小于最小颜色值，答案是 0。

3.2 并查集的实现细节

并查集的实现通常包括三个数组：parent、rank（或 size）、以及一个标记数组 used 来表示格子是否已经被加入。parent 数组存储每个格子的父节点，初始时 parent[i] = i。rank 数组存储每个集合的秩，初始时 rank[i] = 0。used 数组初始时全部为 false。

查找函数 find(x) 使用路径压缩：如果 parent[x] != x，则 parent[x] = find(parent[x])，然后返回 parent[x]。合并函数 union(x, y) 先找到 x 和 y 的根节点，如果相同则返回 false（表示已经在同一个集合中），否则按秩合并：如果 rank[rootX] < rank[rootY]，则 parent[rootX] = rootY；否则如果 rank[rootX] > rank[rootY]，则 parent[rootY] = rootX；否则 rank[rootX]++，parent[rootY] = rootX。合并成功后返回 true。

在本题中，我们还需要维护一个变量 components 来表示当前的连通块总数。初始时 components = 0。每加入一个格子，components 加一。每次成功合并两个集合，components 减一。

3.3 按颜色层处理的完整流程

完整的处理流程如下：

1. 读取 n, m 和颜色矩阵。
2. 收集所有颜色值，去重排序，建立离散化映射。
3. 把颜色矩阵中的每个值替换为离散化后的下标。
4. 把格子按离散化后的颜色值分组，每组存储该颜色的所有格子坐标。
5. 初始化并查集：parent 数组大小为 n*m，初始时 parent[i] = i；rank 数组初始为 0；used 数组初始为 false；components = 0。
6. 准备一个答案数组 ans，大小为离散化后的颜色值数量。
7. 按离散化后的颜色值从小到大遍历：
   • 对于当前颜色的所有格子，标记 used 为 true，components 加一。
   • 对于当前颜色的所有格子，检查四个邻居：如果邻居在网格内、used 为 true、且颜色相同（即离散化后的颜色值相同），则尝试合并。如果合并成功，components 减一。
   • 记录当前颜色值对应的答案 ans[color] = components。
8. 对于每个原始颜色值 c，找到小于等于 c 的最大离散化颜色值，输出对应的 ans。如果不存在，输出 0。

这个流程的时间复杂度是 O(nm α(nm))，空间复杂度是 O(nm)。对于 n,m 达到 1000 的情况，nm 是 10^6，完全可以在 1 秒内运行完成。

3.4 代码实现与关键注释

下面是完整的 C++ 代码实现：

#include <bits/stdc++.h> using namespace std; const int MAXN = 2000005; int parent[MAXN], rnk[MAXN]; bool used[MAXN]; int find(int x) { if (parent[x] != x) parent[x] = find(parent[x]); return parent[x]; } bool unite(int x, int y) { int rx = find(x), ry = find(y); if (rx == ry) return false; if (rnk[rx] < rnk[ry]) swap(rx, ry); parent[ry] = rx; if (rnk[rx] == rnk[ry]) rnk[rx]++; return true; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; vector<vector<int>> a(n, vector<int>(m)); vector<int> allColors; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cin >> a[i][j]; allColors.push_back(a[i][j]); } } // 离散化 sort(allColors.begin(), allColors.end()); allColors.erase(unique(allColors.begin(), allColors.end()), allColors.end()); int C = allColors.size(); // 把颜色替换为离散化后的下标 vector<vector<int>> colorIdx(n, vector<int>(m)); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { colorIdx[i][j] = lower_bound(allColors.begin(), allColors.end(), a[i][j]) - allColors.begin(); } } // 按颜色分组 vector<vector<pair<int,int>>> groups(C); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { groups[colorIdx[i][j]].push_back({i, j}); } } // 初始化并查集 int total = n * m; for (int i = 0; i < total; i++) { parent[i] = i; rnk[i] = 0; used[i] = false; } int components = 0; vector<int> ans(C); int dx[] = {-1, 1, 0, 0}; int dy[] = {0, 0, -1, 1}; for (int c = 0; c < C; c++) { // 先加入当前颜色的所有格子 for (auto [i, j] : groups[c]) { int id = i * m + j; used[id] = true; components++; } // 再检查邻居并合并 for (auto [i, j] : groups[c]) { int id = i * m + j; for (int d = 0; d < 4; d++) { int ni = i + dx[d], nj = j + dy[d]; if (ni < 0 || ni >= n || nj < 0 || nj >= m) continue; int nid = ni * m + nj; if (!used[nid]) continue; if (colorIdx[ni][nj] != c) continue; if (unite(id, nid)) { components--; } } } ans[c] = components; } // 输出对于每个原始颜色值的答案 // 这里假设查询是对于每个出现的颜色值，输出颜色小于等于它的连通块数量 for (int c = 0; c < C; c++) { cout << allColors[c] << " " << ans[c] << "\n"; } return 0; }

这段代码的关键点有几个。第一，离散化时使用了 lower_bound 来找到每个颜色值在排序后列表中的下标。第二，按颜色分组时，使用了 vector 的 vector 来存储每个颜色的所有格子坐标。第三，在加入一个颜色层时，先全部标记 used 并增加 components，然后再统一检查邻居并合并。这样做可以避免因为邻居还没加入而漏掉合并。

第四，在检查邻居时，我们只检查颜色相同的邻居。因为 colorIdx[ni][nj] 存储的是离散化后的颜色值，所以直接比较是否等于当前颜色 c 即可。第五，合并时使用 unite 函数，如果合并成功则 components 减一。

3.5 复杂度分析与优化建议

时间复杂度方面，离散化需要 O(nm log(nm)) 的时间，主要是排序。并查集部分，每个格子最多被加入一次，每次加入时检查四个邻居，合并操作使用路径压缩和按秩合并，总复杂度是 O(nm α(nm))。所以总时间复杂度是 O(nm log(nm))，对于 nm = 10^6 的情况，排序大约需要 2×10^7 次比较，并查集部分大约需要 4×10^6 次操作，完全可以在 1 秒内完成。

空间复杂度方面，parent、rnk、used 数组各需要 O(nm) 的空间，颜色矩阵和 colorIdx 矩阵各需要 O(nm) 的空间，groups 需要 O(nm) 的空间。总空间复杂度是 O(nm)，对于 nm = 10^6 的情况，大约需要几十 MB 的内存，是可以接受的。

优化建议：如果内存比较紧张，可以不用存储 colorIdx 矩阵，而是在检查邻居时直接比较原始颜色值。但这样需要额外判断邻居是否已经加入，以及颜色是否相同。实际上，直接比较原始颜色值也是可以的，因为颜色相同的格子离散化后的下标也相同。所以可以省掉 colorIdx 矩阵，直接使用 a 矩阵来比较颜色。

另外，如果颜色值范围不大，可以不用离散化，直接使用颜色值作为下标。但这样需要开一个大小为最大颜色值的数组，如果最大颜色值很大，会浪费空间。所以离散化是更通用的做法。

4. 常见问题与排查技巧实录

4.1 为什么我的并查集合并后连通块数量不对

这是最常见的问题。通常是因为在加入一个颜色层时，没有先全部加入再统一检查邻居，而是边加入边检查。这样会导致一个问题：如果两个同色格子相邻，但其中一个还没加入，那么当另一个加入时，检查邻居会发现邻居还没加入，所以不会合并。等另一个加入时，它检查邻居会发现第一个已经加入，所以会合并。这样最终结果是对的，但中间过程可能会多算或少算连通块数量。

但更严重的问题是，如果两个同色格子相邻，且它们都在当前颜色层中，那么先加入的那个格子检查邻居时，另一个还没加入，所以不会合并。等另一个加入时，它检查邻居会发现第一个已经加入，所以会合并。这样最终结果是对的。但如果两个同色格子相邻，且它们都在当前颜色层中，但加入顺序是：先加入 A，再加入 B，再检查 A 的邻居，再检查 B 的邻居。这样 A 检查邻居时 B 已经加入，所以会合并。B 检查邻居时 A 已经加入，也会合并。但合并操作是幂等的，第二次合并会返回 false，不会重复减少 components。所以最终结果也是对的。

那为什么还会出错呢？可能是因为在检查邻居时，没有判断邻居的颜色是否相同。如果邻居颜色不同，但 used 为 true，那么就会错误地合并。所以一定要判断颜色相同。

另一个可能的原因是，在合并时没有正确维护 components。每次成功合并应该减一，但如果在合并前没有判断两个格子是否已经在同一个集合中，就会重复减一。所以 unite 函数应该返回是否成功合并，只有成功合并时才减一。

4.2 离散化后颜色值不连续怎么办

离散化后，颜色值变成了 0 到 C-1 的连续整数。但题目要求输出的是对于每个原始颜色值 c 的答案。如果原始颜色值不连续，比如只有 1, 3, 5，那么对于 c=2，答案应该和 c=1 相同，因为颜色小于等于 2 的格子就是颜色小于等于 1 的格子。所以我们需要对于每个查询的 c，找到小于等于 c 的最大原始颜色值，然后输出对应的答案。

如果题目要求输出对于每个原始颜色值的答案，那么只需要输出离散化后每个颜色值对应的答案即可。但如果题目要求输出对于每个可能的 c（从 1 到最大颜色值）的答案，那么就需要对于每个 c，找到小于等于 c 的最大原始颜色值，然后输出对应的答案。如果 c 小于最小颜色值，答案是 0。

4.3 网格边界检查遗漏导致数组越界

在检查邻居时，一定要判断邻居的坐标是否在网格范围内。如果遗漏了边界检查，就会访问到数组之外的内存，导致段错误或错误结果。常见的做法是使用方向数组，然后在循环中判断 ni >= 0 && ni < n && nj >= 0 && nj < m。

另外，如果使用一维编号 im+j，那么邻居的编号是 nim+nj。在判断边界时，可以直接判断 ni 和 nj 的范围，也可以判断编号的范围。但判断编号范围不够准确，因为编号在范围内但坐标可能越界。比如 n=3, m=3，编号 2 对应 (0,2)，编号 3 对应 (1,0)，它们编号相邻但坐标不相邻。所以最好还是判断坐标范围。

4.4 颜色值相同但离散化后下标不同的情况

这种情况不会发生，因为离散化时，相同的颜色值会被映射到同一个下标。但如果颜色值相同但存储方式不同，比如一个存储为 int，一个存储为 long long，可能会导致比较时出现问题。所以最好统一数据类型。

另外，如果颜色值有负数，离散化时也可以正常处理，因为排序和 lower_bound 都支持负数。但需要注意，如果颜色值范围很大，比如达到 10^9，那么离散化是必须的，否则无法开数组。

4.5 常见问题速查表

4.6 独家避坑技巧

第一个技巧是：在加入一个颜色层时，先把该颜色的所有格子都标记为 used 并增加 components，然后再统一检查邻居并合并。这样做可以避免因为加入顺序导致的问题。虽然边加入边检查最终结果也是对的，但统一处理更清晰，不容易出错。

第二个技巧是：在检查邻居时，只需要检查四个方向中的两个方向，比如只检查上和左。因为如果检查四个方向，每条边会被检查两次，虽然不会出错，但会浪费一些时间。只检查上和左可以保证每条边只被检查一次，因为每个格子的上和左邻居如果存在，那么这条边在之前已经被处理过了。但这样做需要确保加入顺序是从上到下、从左到右。如果加入顺序不确定，还是检查四个方向更稳妥。

第三个技巧是：如果颜色值范围不大，可以不用离散化，直接使用颜色值作为下标。但需要先找出最大颜色值，然后开一个大小为最大颜色值+1的数组。如果最大颜色值很大，比如 10^9，那么离散化是必须的。

第四个技巧是：在输出答案时，如果题目要求输出对于每个颜色值 c 的答案，且 c 的范围是 1 到最大颜色值，那么可以对于每个 c，用 lower_bound 找到小于等于 c 的最大原始颜色值，然后输出对应的答案。如果 c 小于最小颜色值，输出 0。这样可以避免对于每个 c 都重新计算。

第五个技巧是：如果题目中有多个测试用例，需要记得清空并查集数组和 used 数组。可以使用 fill 函数或者 memset 来快速清空。但注意 memset 只能用于字节填充，对于 int 数组，只能填充 0 或 -1。所以如果初始值不是 0 或 -1，需要使用 fill。

5. 从这道题延伸出的通用解题框架

5.1 动态连通性问题的分类与解法

动态连通性问题可以分为三类：增量式（只加边）、减量式（只删边）、全动态（加边和删边都有）。增量式问题可以直接用并查集解决。减量式问题可以离线倒序转化为增量式问题。全动态问题比较复杂，通常需要使用 Link-Cut Tree 或者欧拉回路树等高级数据结构，但在算法竞赛中较少出现。

在本题中，我们处理的是增量式问题，因为格子是按颜色从小到大加入的。但如果题目要求的是按颜色从大到小删除格子，那么就是减量式问题，需要离线倒序处理。所以“删边并查集”这个标题实际上是在提示我们：如果遇到删边问题，可以尝试离线倒序，把删边变成加边。

5.2 网格图连通性问题的通用模板

网格图连通性问题的通用模板如下：

1. 把二维坐标映射为一维编号。
2. 定义方向数组。
3. 初始化并查集。
4. 按某种顺序处理格子（加入或删除）。
5. 对于每个格子，检查邻居并合并。
6. 维护连通块数量。
7. 记录答案。

这个模板可以应用于很多问题，比如岛屿数量、最大连通区域、动态连通块计数等。只需要根据具体问题调整处理顺序和合并条件即可。

5.3 离线处理的适用场景与注意事项

离线处理适用于以下场景：操作序列已知，且正向处理困难但反向处理容易。常见的例子包括：删边问题、区间查询问题、历史版本查询问题等。

使用离线处理时需要注意：第一，操作序列必须全部读入后才能开始处理。第二，反向处理时，操作的语义要正确转换，比如删除变成添加，查询变成在某个历史状态下的查询。第三，答案的输出顺序可能需要调整，因为反向处理得到的答案顺序是反的。

在本题中，如果我们采用离线倒序处理，那么需要先把所有格子都加入，然后按颜色从大到小删除格子。但删除格子会导致连通块分裂，并查集无法处理。所以我们需要倒过来，从空图开始按颜色从小到大加入格子。这实际上就是正序处理，不需要离线。所以“删边并查集”这个标题可能只是强调了一种思维转换，而不是说本题必须离线处理。

5.4 并查集在其它领域的应用

并查集不仅仅用于连通性问题，还可以用于很多其它领域。比如：判断无向图中的环、计算最小生成树（Kruskal 算法）、维护等价关系、处理字符串的等价类等。在机器学习中，并查集可以用于聚类算法的实现。在图像处理中，并查集可以用于连通区域标记。

并查集的核心思想是维护一组不相交的集合，支持合并和查找操作。只要问题可以转化为集合的合并和查找，就可以考虑使用并查集。所以掌握并查集的原理和实现，对于解决很多实际问题都有帮助。

5.5 从暴力到优化的思维过程

这道题的暴力解法是：对于每个颜色值 c，遍历所有格子，把颜色小于等于 c 的格子加入图中，然后做一次 BFS 或 DFS 计算连通块数量。时间复杂度是 O(C × nm)，其中 C 是颜色值数量。如果 C 和 nm 都达到 10^6，那么总复杂度是 10^12，完全不可接受。

优化思路是：观察到颜色值 c 增大时，只是加入了一些新的格子，之前的连通块结构并没有被破坏。所以我们可以增量式地维护连通块数量，而不是每次重新计算。这就是并查集的用武之地。通过并查集，我们把每次加入格子的操作均摊到 O(α(nm))，总复杂度降到 O(nm α(nm))。

这个从暴力到优化的思维过程是算法竞赛中非常重要的。很多问题都可以通过观察增量或减量特性，把重复计算的部分用数据结构维护起来，从而降低复杂度。

5.6 代码调试与测试用例设计

在实现这道题时，建议设计一些简单的测试用例来验证正确性。比如：

测试用例 1：1×1 矩阵，颜色为 1。答案应该是对于 c=1，连通块数量为 1。

测试用例 2：2×2 矩阵，颜色全为 1。答案应该是对于 c=1，连通块数量为 1。

测试用例 3：2×2 矩阵，颜色为 1 2 2 1。答案应该是对于 c=1，连通块数量为 2；对于 c=2，连通块数量为 4。

测试用例 4：3×3 矩阵，颜色为 1 1 1 1 2 1 1 1 1。答案应该是对于 c=1，连通块数量为 1（因为颜色 1 的格子形成一个环，但中间有个颜色 2 的格子，所以颜色 1 的格子被分成了两个连通块？不对，颜色 1 的格子是周围一圈，它们通过边相邻，所以是一个连通块。中间的颜色 2 格子是独立的。所以对于 c=1，连通块数量是 1；对于 c=2，连通块数量是 2。

通过这些测试用例，可以验证代码的正确性。如果结果不符合预期，可以逐步调试，检查并查集的合并逻辑、颜色比较逻辑、边界检查等。

5.7 性能调优与常数优化

虽然并查集的复杂度已经很低，但在实际竞赛中，常数优化也很重要。比如：使用 ios::sync_with_stdio(false) 和 cin.tie(nullptr) 来加速输入输出。使用数组而不是 vector 来存储并查集，因为数组访问更快。使用 inline 关键字来提示编译器内联函数。使用 register 关键字（虽然现代编译器会自动优化）来提示变量存储在寄存器中。

另外，如果颜色值范围不大，可以不用离散化，直接使用颜色值作为下标，这样可以省掉排序和 lower_bound 的时间。如果颜色值范围很大，但出现的颜色值数量不多，离散化是必要的。

在检查邻居时，可以使用方向数组和循环，也可以手动展开四个方向。手动展开可以减少循环开销，但代码会变得冗长。通常使用方向数组就足够了。

5.8 类似题目的推荐与练习建议

如果这道题做完了，可以尝试以下类似题目来巩固：

第一类：网格图上的连通块计数，比如“岛屿数量”、“最大岛屿面积”等。这些题目通常用 BFS 或 DFS 解决，但也可以用并查集。

第二类：动态连通性问题，比如“朋友圈”、“连通网络的操作次数”等。这些题目通常用并查集解决。

第三类：离线倒序处理问题，比如“删除操作后的连通块数量”、“历史版本查询”等。这些题目需要把删除变成添加，然后用并查集解决。

第四类：带权并查集问题，比如“食物链”、“奇偶游戏”等。这些题目需要在并查集中维护额外的信息。

通过练习这些题目，可以加深对并查集的理解，掌握更多变体和解法。

5.9 从竞赛题到工程实践的迁移

虽然这道题是算法竞赛题，但它的解题思路在工程实践中也有应用。比如：在社交网络中，动态维护用户之间的连通关系；在图像处理中，动态维护像素的连通区域；在网络管理中，动态维护设备的连通性。这些场景都可以使用并查集来维护连通块数量。

另外，离线倒序处理的思路在工程中也有应用。比如：在数据库系统中，处理删除操作时，可以先把删除操作记录下来，然后定期批量执行，而不是每次删除都立即更新索引。这样可以提高性能。

所以，学习算法竞赛题不仅仅是为了比赛，更是为了培养解决问题的思维方式和编程能力。这些能力在工程实践中同样重要。

5.10 个人实操心得与建议

我在实现这道题时，踩过几个坑。第一个坑是：在加入一个颜色层时，没有先全部加入再统一检查邻居，而是边加入边检查。结果导致有些同色相邻格子没有被合并，连通块数量偏大。后来改成先全部加入再统一检查，问题就解决了。

第二个坑是：在检查邻居时，没有判断邻居的颜色是否相同，导致不同颜色的格子被错误合并，连通块数量偏小。后来加上颜色比较，问题就解决了。

第三个坑是：在离散化时，没有正确处理颜色值不连续的情况，导致输出答案时找不到对应的颜色值。后来使用 lower_bound 找到小于等于查询颜色值的最大原始颜色值，问题就解决了。

第四个坑是：在输出答案时，没有按照题目要求的顺序输出，导致答案错误。后来仔细阅读题目，确认输出格式，问题就解决了。

所以，做这类题目时，一定要仔细阅读题目，理解题意，然后设计清晰的实现方案。在实现过程中，要注意边界条件、颜色比较、合并逻辑等细节。最后，用简单的测试用例验证正确性，确保代码没有问题。