求解无向图的极大连通块数量 - 优化版

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

注意 1<=n<=100000.

一个连通块是指在一个无向图中的一个子图，其中任意两个顶点之间存在路径。而极大连通块是指在一个连通块中，不存在其他顶点与该连通块的顶点相连。

我们可以使用深度优先搜索（DFS）来解决这个问题。

首先，我们需要按照给定的点的坐标进行排序。排序的规则是首先按照x坐标升序排列，若x坐标相同则按照y坐标升序排列。

然后，我们创建一个空的图，用邻接表的形式表示。然后，我们开始遍历排好序的点。

对于每个点，我们使用DFS来找到与该点连通的所有点，并将它们标记为已访问。在DFS的过程中，我们只考虑满足x[i]<=x[j]并且y[i]<=y[j]的边。

最后，我们统计有多少个连通块，即有多少个DFS的遍历。

以下是解决这个问题的Python代码示例：

def dfs(graph, node, visited):
    visited[node] = True
    for neighbor in graph[node]:
        if not visited[neighbor]:
            dfs(graph, neighbor, visited)

def count_max_connected_components(points):
    n = len(points)
    graph = [[] for _ in range(n)]
    visited = [False] * n

    # Sort points by x coordinate and then y coordinate
    points = sorted(points, key=lambda x: (x[0], x[1]))

    for i in range(n):
        for j in range(i+1, n):
            if points[i][0] <= points[j][0] and points[i][1] <= points[j][1]:
                # Add edge between points[i] and points[j]
                graph[i].append(j)
                graph[j].append(i)

    count = 0
    for i in range(n):
        if not visited[i]:
            dfs(graph, i, visited)
            count += 1

    return count

# Example usage:
points = [(1, 2), (3, 4), (2, 3), (4, 5)]
result = count_max_connected_components(points)
print(result)  # Output: 2

在这个示例中，给定的点是[(1, 2), (3, 4), (2, 3), (4, 5)]。首先，我们对这些点进行排序得到[(1, 2), (2, 3), (3, 4), (4, 5)]。

然后，我们创建一个空的图，通过遍历排好序的点，并根据满足条件的边添加边。最后，我们使用DFS进行连通性遍历，并统计有多少个连通块。

在这个示例中，有两个极大连通块，所以输出结果是2。