求解点集中的极大连通块数量 - 并查集算法详解 - 常规

给定n个点(x[i], y[i])，对于两个点(x[i], y[i])和(x[j], y[j])，若有 x[i]<=x[j] 且 y[i]<=y[j]，这两个点之间有一条无向边。求有多少个极大连通块。

注意 1<=n<=100000.

极大连通块是指在一个连通块内，不存在其他的点与该连通块中的点连通。

我们可以使用并查集来解决这个问题。首先，将所有的点按照x坐标从小到大排序，若x坐标相等则按照y坐标从小到大排序。然后，遍历所有的点，对于每个点(x[i], y[i])，如果存在点(x[j], y[j])满足x[j]>=x[i]且y[j]>=y[i]，则将两个点合并到同一个连通块中。最后，统计有多少个不同的连通块即可。

具体实现步骤如下：

定义一个数组parent，用于存储每个点的父节点。
定义一个函数find，用于查找某个点的根节点。
1. 如果点x的父节点不是自己，则递归查找父节点的根节点。
2. 将点x的父节点更新为根节点。
3. 返回根节点。
定义一个函数union，用于合并两个点所在的连通块。
1. 分别找到两个点的根节点，如果根节点不同，则将其中一个根节点的父节点更新为另一个根节点。
定义一个变量count，用于记录连通块的数量，初始值为n。
对所有的点进行遍历，按照(x[i], y[i])的顺序。
1. 如果点(x[i], y[i])的父节点不是自己，则将count减1。
2. 将点(x[i], y[i])的父节点更新为自己。
3. 分别判断点(x[i], y[i])的右边和上边的点是否存在且满足条件。如果满足条件，则调用union函数合并两个点所在的连通块。
返回count的值。

以下是具体实现的示例代码：

def find(x, parent):
    if parent[x] != x:
        parent[x] = find(parent[x], parent)
    return parent[x]

def union(x, y, parent, count):
    root_x = find(x, parent)
    root_y = find(y, parent)
    if root_x != root_y:
        parent[root_x] = root_y
        count -= 1
    return count

def max_connected_blocks(points):
    n = len(points)
    parent = [i for i in range(n)]
    count = n
    
    points.sort(key=lambda x: (x[0], x[1]))
    
    for i in range(n):
        x, y = points[i]
        if parent[i] != i:
            count -= 1
        parent[i] = i
        
        if i < n - 1 and points[i+1][0] >= x and points[i+1][1] >= y:
            count = union(i, i+1, parent, count)
        if i > 0 and points[i-1][0] <= x and points[i-1][1] <= y:
            count = union(i, i-1, parent, count)
    
    return count

# 测试案例
points = [(1, 2), (2, 1), (2, 2), (3, 1), (3, 2), (3, 3)]
print(max_connected_blocks(points))  # 输出2

对于给定的n个点，时间复杂度为O(nlogn)，空间复杂度为O(n)。