S'S ALGORITHM

概念和适用范围

概念上来说，它关注的是将树节点，按照高度进行合并。对一棵用edges表述的树来说，具体合并过程，相当于将每一个子节点都不断的向上合并，直到所有的节点都被压扁到他们共享一个父亲节点。这样以来如果有任何想要连接子节点，而不共享父节点的边，都是那个构成环的边，也就是冗余的边。

适用问题：

• 根据某种属性对元素进行分组，即将具有相同属性的元素划分到连通分量中。相当于将不同的节点，划分给不同的父节点。
• 需要将初始给定的不相交的集合两两合并，或判断两个元素是否属于同一集合。
• 虽然问题的数据最适合用图的形式组织，但输入数据并非邻接表/矩阵的形式，需要进行数据转换和组织。

现实世界问题：

• 图像分割和区域合并: 通过将相邻相似颜色的像素合并成区域，来对数字图像进行分割。并查集可以跟踪每个像素所属的区域，并在区域合并时更新信息。
• 图像处理: 图像编辑应用中使用并查集来定位图像中不同的对象，实现选择区域、区分前景背景等功能。
• 网络连通性: 判断两个设备之间是否存在连通路径。
• 渗流: 确定液体通过滤波器的渗透阈值。使用NxN网格模拟滤波器，并查集连接相邻开放区域，若存在从顶部到底部的连通分量，则可渗流。
• 六角棋游戏: 通过连接同色棋子，判断哪个玩家获胜。

很好，很复杂。并查集本身就是一个高级的主题。在实际应用中联想，完全不如在算法问题中这么明晰，重要的是在实际中，不断的找到算法的影子。将理论和实践结合。

总的来说，并查集，和联通，冗余，分组问题相关，在遇到这些问题的时候，可以考虑运用。

问题1:Redundant Connection

该问题中，tree被定义为，无向无环图。你被给定了一个图，有 n 个节点，从 1 到 n，但是在这个图中，被加入了一条冗余的边，这条边被 1 到 n 中两个不同的端点连接。返回可以删除的边，以便生成的图是 n 节点树。如果有多个答案，则返回输入列表中最后出现的符合条件的答案。

比如，给定edges = [[1, 2],[1, 3],[2, 3]]， 输出[2, 3]

其实这是一个典型的，自己组装并查集的题，通过这道题正好可以切入并查集的基础结构。代码如下：

class Solution(object):
    def findRedundantConnection(self, edges):
        """
        :type edges: List[List[int]]
        :rtype: List[int]
        """
        # 初始化父节点为该节点自己
        par = [i for i in range(len(edges) + 1)]
        # 将每个节点的高度设置为1
        rank = [1] * (len(edges) + 1)

        def find(n):
            """
            helper函数，是为了在下面的步骤中，用于找到节点的父节点
            while的部分表示，当自己的父节点不是自己的时候，就不断的将父节点的父节点，设置为该节点的父节点
            是一种压缩树高度的行为，最终找到父节点，即为该节点自己
            """
            p = par[n]
            while p != par[p]:
                par[p] = par[par[p]]
                p = par[p]
            return p

        def union(n1, n2):
            """
            union是用来进行合并的部分
            找到这两个节点的父节点，然后比较树的高度，将低的树合并到高的树上，并重新计算高度
            如果他们已经共享父节点了就不需要何必了
            return的，是否进行了合并
            """
            p1, p2 = find(n1), find(n2)

            if p1 == p2:
                return False
            
            if rank[p1] > rank[p2]:
                par[p2] = p1
                rank[p1] += rank[p2]
            else:
                par[p1] = p2
                rank[p2] += p1
            return True

        # 通过union返回值判断两个节点是否已经有同样的父节点
        # 如果有的话说明再连接就冗余了，返回该节点即可
        for n1, n2 in edges:
            if not union(n1, n2):
                return [n1, n2]

笔记：这是一道逻辑非常清晰的题，不再赘述。时间复杂度和空间复杂度都是O(n)。

这是因为在进行find和union的时候，它的时间复杂度都是阿克曼反函数大小。

时间复杂度O(α(n))中的α(n)是阿克曼反函数(Ackermann inverse function)的渐进记号表示。

阿克曼函数是一个数论函数,增长非常快,被用来定义计算复杂性理论中所需的差值级。α(n)是阿克曼函数的反函数,它是一种极其缓慢增长的函数。

具体来说:

• α(n)是一个非常缓慢增长的函数,它的实际值非常小,在实际应用中很少大于4。
• 对任何可以用现有计算机资源精力计算的n值,α(n)的值都不超过5。
• 任何实际运行的合理算法的时间复杂度都不会比α(n)更慢。

因此,O(α(n))被认为是计算复杂性理论中的一个很好的渐进记号,用来表示一个非常优秀、高效的算法,它的运行时间基本上可以认为是一个很小的常数。并查集的时间复杂度就是这个量级。

总之,O(α(n))反映了一种极其高效、接近最优的算法时间复杂度,实际应用意义重大。

问题2:Last Day Where You Can Still Cross

困难难度的力扣题。

给定一个由格子组成的二维地图，其中包含了陆地（用0表示）和水（用1表示）。在第一天都是陆地，但是每一天都有一个格子被水淹没。假设你可以在道路上自由移动，但不能斜着走。你从地图的最上方的某个起始位置出发，要前往地图的最下方。问题是在给定的淹水条件下，你哪天是最后能通过格子的。

比如cells = [[1, 1],[2, 1],[1, 2],[2, 2]]，比如该cells给定的就是第index天，淹水的格子。结果应当返回2，这是因为在第三天开始无法通过格子。所以第二天是最后期限（第0天是初始天）。

同样是使用并查集思路：

以下是代码的思路步骤：

• 初始化数据结构：计算总格子数 n。初始化并查集的 root，left 和 right 列表。
• 填充 left 和 right 列表：遍历每一列和每一行，将每个格子对应的列数填充到 left 和 right 列表中，使其初始值为当前列数。
• 定义并查集的 find 和 union 函数：find(x) 函数用于找到节点 x 所在连通分量的根节点。union(x, y) 函数用于合并节点 x 和 y 所在的连通分量，并更新合并后连通分量的边界。
• 初始化其他变量：初始化一个集合 seen 用于存储已经遍历过的格子。定义一个方向数组 dirs，用于表示上、下、左、右、以及四个对角线的移动方向。
• 遍历每个格子：
  • 对于每个格子，首先将其添加到 seen 集合中。
  • 遍历每个格子周围的相邻格子：
    • 若相邻格子在 seen 集合中，表示当前格子和相邻格子可以合并为一个连通分量，调用 union 函数进行合并。
    • 合并后，检查合并后连通分量的边界是否满足条件，若满足则返回当前天数。
  • 若遍历完所有格子都未找到满足条件的天数，则返回格子总数。

整体思路是利用并查集算法来合并连通分量，并通过维护每个连通分量的边界来判断是否满足条件。算法的核心是遍历格子并进行合并操作，以及检查合并后的连通分量的边界是否满足条件。

class Solution:
    def latestDayToCross(self, row, col, cells):
        n = row * col
        # root是根节点，每个节点都指向自己，left和right是最左和最右边界
        root, left, right = list(range(n)), [0] * n, [0] * n

        # 使用格子索引更新左右边界的列表，所谓边界是指格子所在位置的col
        for i in range(col):
            for j in range(row):
                # [0, 0, 1, 1]
                left[i * row + j] = i
                right[i * row + j] = i

        # find找到根节点
        def find(x):
            if x != root[x]:
                root[x] = find(root[x])
            return root[x]

        # 合并连通分量，返回左右边界
        def union(x, y):
            a, b = find(x), find(y)
            if a != b:
                root[a] = b
            left[b] = min(left[b], left[a])
            right[b] = max(right[b], right[a])

        # 开始搜索
        seen = set()
        dirs = ((1, 0), (0, 1), (-1, 0), (0, -1),
                (1, 1), (-1, 1), (1, -1), (-1, -1))

        for i, cell in enumerate(cells):
            cx, cy = cell[0] - 1, cell[1] - 1
            for dx, dy in dirs:
                x, y = cx + dx, cy + dy
                #检查相邻格子的有效性和是否见过
                if 0 <= x < row and 0 <= y < col and (x, y) in seen:
                    # union两个格子
                    union(cy * row + cx, y * row + x)
                    # 找到合并后的根节点
                    new = find(y * row + x)
                    # 检查新的组合是否可以跨越边界
                    if left[new] == 0 and right[new] == col - 1:
                        # 为真则返回天数
                        return i
            seen.add((cx, cy))

        return n

学习笔记：时间复杂度和空间复杂度O(mxn)。