题解 | 省份数量

题干解析

剥离题设背景即：给出一个图的邻接矩阵，求这个图有多少个联通分量

算法思路

本题是有关并查集的典型应用。同时我们注意到，我们在构建图时，任意增添一条从一个联通分量去往另一个联通分量的边都会导致两个联通分量合并为一个，因此总联通分量减少一个，初始无边的图联通分量为点的个数。同时并查集数据结构又十分便于我们进行是否在同一个联通分量的判断。

实现代码

class L547 {
    class UnionFind {
        vector<int> parent;

    public:
        explicit UnionFind(const int n) : parent(n) {
            for (int i = 0; i < n; ++i) parent[i] = i;
        }

        int find(int x) {
            while (parent[x] != x) {
                parent[x] = parent[parent[x]];
                x = parent[x];
            }
            return x;
        }

        void link(const int x, const int y) {
            const int rootX = find(x), rootY = find(y);

            if (rootX == rootY) return;
            parent[rootX] = rootY;
        }

        bool isLinked(const int x, const int y) {
            return find(x) == find(y);
        }
    };

public:
    int findCircleNum(vector<vector<int> > &isConnected) {
        const int n = static_cast<int>(isConnected.size());
        UnionFind uf(n);
        int cnt = n;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (isConnected[i][j] && !uf.isLinked(i, j)) {
                    uf.link(i, j);
                    --cnt;
                }
            }
        }
        return cnt;
    }
};

复杂度分析

• 时间复杂度：针对并查集的查询每次最坏时间复杂度为，平均为，总计查询次数为，其中为常数，因此时间复杂度最坏为,平均为其中 为阿克曼函数的反函数，可以认为是一个很小的常数。
• 空间复杂度：主要额外空间消耗为并查集中的parent数组，因此空间复杂度为。