连通分量个数：并查集的应用

在图论中，连通分量是一个重要的概念。在无向图中，如果从顶点vi到顶点vj有路径，则称vi和vj连通。一个连通分量是一个最大的连通子图，即如果从该子图的任意一个顶点出发都能到达该子图的任意另一个顶点。而一个非连通图则由若干个连通分量组成。

对于一个包含N个顶点和M条边的无向图，如何快速地计算其连通分量的个数呢？我们可以使用并查集这一数据结构。

并查集主要用于处理一些不相交集合的合并与查询问题。其基本操作包括：
1）查找：判断某元素属于哪个集合；
2）合并：将两个集合合并为一个集合。

并查集的查找操作的时间复杂度为O(1)，而合并操作的时间复杂度为O(N)，其中N为总元素个数。因此，通过使用并查集，我们可以高效地计算出连通分量的个数。

首先，初始化每个顶点为一个独立的集合。然后，遍历图的每条边，对于每条边(u, v)，如果它们属于不同的集合，则将这两个集合合并，并将连通分量个数加一。遍历完所有边后，连通分量个数即为所求。

具体实现上，我们可以使用数组来表示并查集，数组的每个元素表示一个集合的根节点。通过判断两个元素是否相等，可以判断两个顶点是否属于同一个集合，也就是是否连通。通过将一个元素的父指针指向另一个元素，可以实现合并操作。

以下是使用Python实现的一个简单示例：

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n  # 记录每个集合的秩，用于路径压缩优化