如何在O(1)时间内检测动态更新矩阵首尾行的连通性？

核心思路是用带路径压缩和按秩合并的并查集维护所有1单元格的连通分量，同时引入两个虚拟节点分别关联第一行和最后一行的连通区域，每次更新后只需近似O(1)的常数时间查询两个虚拟节点是否连通即可。

具体实现步骤 #

1. 并查集初始化

   • 给n×n矩阵的每个单元格分配唯一标识：单元格(i,j)可映射为i*n + j；额外添加两个虚拟节点：top（标识为n*n）和bottom（标识为n*n + 1）。
   • 初始化并查集，每个节点的父节点指向自身，秩（或大小）初始为1。

2. 置1操作的处理逻辑

   • 当选中单元格(i,j)并置为1后：
     • 若i是第一行（i=0），将该单元格标识与top节点合并；若i是最后一行（i=n-1），将该单元格标识与bottom节点合并。
     • 遍历该单元格的8个邻接单元格（上下左右、四个对角线），对每个在矩阵范围内且已被置为1的邻接单元格(x,y)，执行当前单元格与(x,y)的合并操作。

3. 连通性判断

   • 每次操作完成后，调用并查集的find方法，查询top和bottom的根节点是否相同。若相同则第一行与最后一行已连通，否则未连通。该查询操作因路径压缩和按秩合并的优化，实际复杂度接近常数。

关键细节说明 #

• 边界处理：遍历8邻接单元格时需判断坐标是否在矩阵范围内，避免越界访问。
• 重复选择处理：若选中已为1的单元格，直接跳过合并操作，返回当前连通性结果即可。
• 并查集优化必要性：路径压缩和按秩合并是保证合并、查询操作接近常数时间的核心，必须实现这两个优化才能满足O(1)判断的需求。

对比原有方法的优势 #

原有递归遍历最新修改单元格的方法每次需O(n)时间，而本方案中每次置1操作最多执行8次合并（对应8个邻接单元格），每次合并接近O(1)，最终连通性判断直接是近似O(1)的查询，整体效率远高于原有方案。

内容的提问来源于stack exchange，提问作者ZirconPetrichor