day53 图论章节刷题Part05（并查集理论基础、寻找存在的路径）

1. 引言

图论（Graph Theory）是离散数学中一个重要的研究领域。图论应用广泛，不仅在计算机科学中占据着重要位置，而且在网络通信、社交网络、人工智能等领域也具有重要的应用。本文主要聚焦于“并查集”这一数据结构的基础理论与应用，探索如何通过并查集寻找图中的存在路径，并结合实例深入理解并查集的具体操作与实践。

并查集（Union-Find Set），又称为不相交集合（Disjoint Set），是一种数据结构，用于处理集合的合并（union）和查询（find）操作。并查集结构在图论中广泛应用，特别是在寻找连接路径、判断图的连通性、最小生成树等问题中。本文将通过详细的理论讲解和实际刷题案例，帮助读者掌握并查集的基本操作、优化技巧以及如何利用并查集解决图中的路径寻找问题。

2. 并查集基本概念与操作

2.1 并查集的基本结构

并查集是一种用于处理不相交集合的数据结构，它主要包含以下几个基本操作：

Find(x)：查找元素 x 所在的集合，并返回该集合的代表元素（通常是集合的根节点）。
Union(x, y)：将包含元素 x 和元素 y 的两个集合合并成一个集合。
Connected(x, y)：判断元素 x 和元素 y 是否属于同一个集合。

并查集的设计核心在于通过一系列的路径压缩与按秩合并（Union by Rank）操作，使得集合的查找与合并操作尽可能地高效。

2.2 并查集的实现

并查集通常使用一个数组来表示，其中每个元素存储的是该元素的父节点（若该元素是根节点，则父节点指向自己）。在执行 find 操作时，我们通过不断追踪父节点，直到找到根节点。而在执行 union 操作时，我们将两个集合的根节点合并，通常会选择较小的根节点合并到较大的根节点下，或通过“按秩合并”策略来决定合并方式。

并查集的核心思想是利用树的结构来表示集合，通过路径压缩和按秩合并来优化查询和合并操作，从而大大提高效率。

pythonCopy Code
class UnionFind:
    def __init__(self, n):
        # 初始化父节点数组和秩数组
        self.parent = list(range(n))  # parent[i] 表示 i 的父节点
        self.rank = [1] * n           # rank[i] 表示以 i 为根的树的高度

    def find(self, x):
        # 路径压缩：递归查找并使路径上的每个节点指向根节点
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # 递归查找并进行路径压缩
        return self.parent[x]

    def union(self, x, y):
        # 合并两个集合，按秩合并
        rootX = self.find(x)
        rootY = self.find(y)

        if rootX != rootY:
            if self.rank[rootX] > self.rank[rootY]:
                self.parent[rootY] = rootX
            elif self.rank[rootX] < self.rank[rootY]:
                self.parent[rootX] = rootY
            else:
                self.parent[rootY] = rootX
                self.rank[rootX] += 1

    def connected(self, x, y):
        # 判断两个元素是否属于同一个集合
        return self.find(x) == self.find(y)

2.3 并查集操作的时间复杂度

find(x) 的时间复杂度：O(α(n))，其中 α(n) 是阿克曼函数的反函数，增长极其缓慢，因此近似为常数时间。
union(x, y) 的时间复杂度：O(α(n))。
connected(x, y) 的时间复杂度：O(α(n))。

因此，使用路径压缩与按秩合并优化后的并查集操作几乎可以视作常数时间复杂度。

3. 路径寻找与并查集应用

3.1 路径寻找问题的背景

在图论中，路径寻找问题是一个常见的基本问题。给定一个图，我们希望能够判断从某个起点是否能够到达某个终点，或者找到一条从起点到终点的路径。对于某些图，如无向图，路径寻找问题可以通过并查集来有效地解决。

3.2 场景实例：判断图是否为连通图

给定一个无向图，判断图是否是连通图，即图中的任意两点是否都有路径相连。如果图中的任意两点之间都有路径，则图是连通的；否则，图是不连通的。

实现思路：

初始化并查集，将每个节点视为一个独立的集合。
对于每一条边，执行 union 操作将两个节点合并到同一个集合中。
最后，检查所有节点是否都属于同一个集合，如果是，则图是连通的，否则图是不连通的。

pythonCopy Code
def isConnected(n, edges):
    uf = UnionFind(n)
    for u, v in edges:
        uf.union(u, v)
    
    # 判断是否所有点都属于同一集合
    root = uf.find(0)
    for i in range(1, n):
        if uf.find(i) != root:
            return False
    return True

# 示例
n = 5
edges = [(0, 1), (1, 2), (3, 4)]  # 图中有一条断开的边，图不连通
print(isConnected(n, edges))  # 输出: False

3.3 场景实例：查找是否存在路径

假设我们有一个无向图，图的节点表示城市，边表示城市间的道路。给定两个城市，问这两个城市之间是否存在一条路径。我们可以通过并查集来判断。

实现思路：

初始化并查集，将每个城市视为一个独立的集合。
对于每一条道路，执行 union 操作将两个城市合并到同一个集合中。
最后，执行 find 操作检查两个城市是否属于同一个集合，如果是，则存在路径。

pythonCopy Code
def isPathExists(n, roads, city1, city2):
    uf = UnionFind(n)
    for u, v in roads:
        uf.union(u, v)
    
    return uf.connected(city1, city2)

# 示例
n = 6
roads = [(0, 1), (1, 2), (2, 3), (4, 5)]  # 城市间的道路
print(isPathExists(n, roads, 0, 3))  # 输出: True，城市0到城市3之间有路径
print(isPathExists(n, roads, 0, 5))  # 输出: False，城市0到城市5之间没有路径

3.4 并查集优化：路径压缩与按秩合并

在并查集的实际应用中，路径压缩和按秩合并是两个重要的优化策略。通过这两种技术，我们可以使得并查集的操作接近常数时间，极大地提高了效率。

路径压缩：在执行 find 操作时，将路径上的所有节点直接连接到根节点上，避免了重复查找，提高了查询效率。
按秩合并：在执行 union 操作时，总是将较小的树合并到较大的树上，从而保持树的平衡，避免出现过深的树。

这两种优化策略结合使用后，可以确保并查集在大规模数据集上的高效性。

4. 刷题实践与应用场景

通过刷题，掌握并查集的具体应用，尤其是在图论问题中的路径寻找问题，可以帮助我们更好地理解图的结构和优化算法。

4.1 题目：岛屿的数量

题目描述：

给定一个二维的网格，表示一个地图，其中 1 表示陆地，0 表示水域。岛屿是由水平方向和垂直方向上的陆地相连组成的。求岛屿的数量。

解决思路：

我们可以将每个陆地视为一个节点，每对相邻的陆地连接一条边。
使用并查集将相连的陆地合并在一起。
最后，统计并查集中的根节点个数，即为岛屿的数量。

pythonCopy Code
def numIslands(grid):
    if not