947. 同行或同列移除最多石头
内容提要
给定一个二维平面上的石头数组，使用DFS方法找到可以移除的最大石头数量。移除条件是石头共享相同的行或列。返回移除的最大石头数量。
延伸解读
连通分量与可移除石头数的关系
文章指出，最大可移除石头数等于总石头数减去连通分量数。这是因为每个连通分量中，最终至少会剩下一块石头无法移除，而其余石头都可以通过共享行或列被依次移除。理解这一关系是解题的关键，它避免了模拟移除过程，直接转化为图论中的连通性问题。
DFS 在连通分量查找中的应用
解决方案使用深度优先搜索（DFS）来标记同一连通分量中的所有石头。从每个未访问的石头出发，DFS 会递归访问与其共享行或列的所有石头，从而完整地探索一个连通分量。这种方法直观且易于实现，但需要注意递归深度可能达到石头数量，在极端情况下可能导致栈溢出。
算法复杂度与约束适应性
文章给出的时间复杂度为 O(n^2)，空间复杂度为 O(n)。由于石头数量 n 最大为 1000，O(n^2) 的算法在时间上是可行的。但需注意，DFS 实现中检查行或列连接时可能涉及嵌套循环，实际运行效率取决于具体实现。在 n=1000 时，最坏情况下约百万次操作，仍在可接受范围内。
边界情况与示例验证
文章通过三个示例验证了算法：示例1输出5，示例2输出3，示例3输出0。这些例子覆盖了多连通分量、单连通分量和单石头的情况。特别地，示例2中石头 [1,1] 是孤立的，因此无法移除，这提醒我们注意孤立点对结果的影响。算法能正确处理这些边界情况，增强了可靠性。
Q&A
如何在二维平面上移除最多的石头？
可以通过深度优先搜索（DFS）方法找到可以移除的最大石头数量，条件是石头共享相同的行或列。
给定的石头数组如何影响可移除的石头数量？
石头数组的布局决定了可以移除的石头数量，连接的石头组件越多，可移除的石头数量越少。
示例中可以移除多少个石头？
在示例1中可以移除5个石头，在示例2中可以移除3个石头，而在示例3中无法移除任何石头。
DFS方法在解决这个问题中有什么作用？
DFS方法用于探索同一连接组件中的所有石头，帮助计算可移除的最大石头数量。
这个问题的时间复杂度和空间复杂度是多少？
时间复杂度为O(n^2)，空间复杂度为O(n)。
如何计算可移除的最大石头数量？
可移除的最大石头数量等于总石头数量减去连接组件的数量。
