力扣547题 解题思路和步骤 C++代码实现,c++入门基础题

问题建模与算法选择

力扣547题要求计算省份数量，本质是图论中的连通分量问题。给定n个城市构成的邻接矩阵，我们需要确定相互连通的城市集合数量。此类问题最典型的解法包括深度优先搜索（DFS）、广度优先搜索（BFS）和并查集（Union-Find）。其中并查集凭借其接近线性的时间复杂度，在处理大规模数据时具有显著优势。

并查集的核心思想是通过维护父节点数组实现集合合并与查询操作。每个城市初始视为独立集合，遍历邻接矩阵时合并相连城市，最终统计根节点数量即为省份总数。这种方法将问题时间复杂度从DFS的O(n²)优化至O(n²α(n))，其中α(n)是阿克曼函数的反函数，实际应用中可视作常数级。

并查集核心操作解析

并查集的实现需要两个核心操作：查找（Find）与合并（Union）。查找操作用于确定元素的根节点，合并操作将两个集合合并为单个集合。为提高效率，需要采用路径压缩和按秩合并两种优化策略。

路径压缩通过在查找过程中将节点直接连接到根节点，缩短后续查询路径。按秩合并则始终将较小的树合并到较大的树上，避免树的高度过度增长。这两种优化共同作用，使得每次操作的时间复杂度接近O(1)。

代码实现与复杂度分析

class UnionFind {
private:
    vector parent;
    vector rank;
    int count;
public:
    UnionFind(int n) : parent(n), rank(n, 1), count(n) {
        iota(parent.begin(), parent.end(), 0);
    }
    int find(int x) {
        return parent[x] == x ? x : parent[x] = find(parent[x]);
    }
    void unite(int x, int y) {
        x = find(x);
        y = find(y);
        if(x == y) return;
        if(rank[x] < rank[y]) swap(x, y);
        parent[y] = x;
        rank[x] += (rank[x] == rank[y]);
        --count;
    }
    int getCount() const { return count; }
};
int findCircleNum(vector>& isConnected) {
    int n = isConnected.size();
    UnionFind uf(n);
    for(int i = 0; i < n; ++i)
        for(int j = i+1; j < n; ++j)
            if(isConnected[i][j])
                uf.unite(i, j);
    return uf.getCount();
}

该实现的时间复杂度为O(n²α(n))，空间复杂度O(n)。邻接矩阵的遍历需要O(n²)时间，而每个并查集操作的时间复杂度由阿克曼函数的反函数决定，实际应用中可视作常数级。

测试用例验证

通过三个典型测试用例验证算法正确性：
1. 完全连通情况：输入[[1,1],[1,1]]，输出应为1
2. 全不连通情况：输入[[1,0],[0,1]]，输出应为2
3. 混合连通情况：输入[[1,1,0],[1,1,0],[0,0,1]]，输出应为2

本文系统性地解析了力扣547题的并查集解法，通过路径压缩和按秩合并实现高效连通分量统计。代码实现兼顾可读性与性能，测试验证覆盖各类边界条件。该方案在时间空间复杂度上达到理论最优，适用于处理大规模城市网络问题，可作为同类连通性问题的通用解决方案。