跳转至

547 省份数量

解法一:dfs

本题nxn矩阵可视作邻接矩阵,对其可以进行图论的dfs或bfs遍历,找出所有的连通分量

关键在于如果计算连通分量的个数:如果第i - 1次dfs遍历后仍有节点没有被遍历,说明其属于新的连通分量

class Solution {
private:
    void dfs(vector<vector<int>>& isConnected, vector<bool>& isVisited, int idx){
        for(int j = 0; j < isConnected[idx].size(); j++){
            if(isConnected[idx][j] && !isVisited[j]){
                isVisited[j] = true;
                dfs(isConnected, isVisited, j);
            }
        }
    }
public:
    int findCircleNum(vector<vector<int>>& isConnected) {
        int n = isConnected.size();
        vector<bool> isVisited(n, false);
        int ans = 0;
        for(int i = 0; i < n; i++){
            // 遍历一遍后,如果第二遍还出现了没有遍历过的节点
            // 说明出现新的连通分量
            if(!isVisited[i]){
                // 找出i对应的所有连通节点,对其标记
                dfs(isConnected, isVisited, i);
                // i没有被访问过,所以出现新的连通分量
                ans++;
            }
        }
        return ans;
    }
};

复杂度分析

时间复杂度:\(O(n^2)\),其中 n 是城市的数量。需要遍历矩阵 n 中的每个元素。

空间复杂度:\(O(n)\),其中 n 是城市的数量。需要使用数组 visited 记录每个城市是否被访问过,数组长度是 n,递归调用栈的深度不会超过 n

解法二: bfs

与dfs类似,以每个节点bfs遍历一遍,如果遍历停止,说明其访问完所有相连的节点

遍历后还有未访问的节点,说明有新的连通分量

class Solution {
public:
    int findCircleNum(vector<vector<int>>& isConnected) {
        int n = isConnected.size();
        vector<bool> isVisited(n, false);
        int ans = 0;
        for(int i = 0; i < n; i++){
            queue<int> q;
            if(!isVisited[i]){
                ans++;
                q.push(i);
                while(!q.empty()){
                    int idx = q.front();
                    q.pop();
                    for(int j = 0; j < n; j++){
                        if(isConnected[idx][j] && !isVisited[j]){
                            q.push(j);
                            isVisited[j] = true;
                        }
                    }
                }
            }
        }
        return ans;
    }
};

复杂度分析

时间复杂度:\(O(n^2)\),其中 n 是城市的数量。需要遍历矩阵 isConnected 中的每个元素。

空间复杂度:\(O(n)\),其中 n 是城市的数量。需要使用数组 visited 记录每个城市是否被访问过,数组长度是 n,广度优先搜索使用的队列的元素个数不会超过 n。

解法三: 并查集

class Solution {
public:
    int Find(vector<int>& p, int x) {
        if (p[x] != x)
            p[x] = Find(p, p[x]);
        return p[x];
    }
    void Union(vector<int>& p, int x, int y) { p[Find(p, x)] = Find(p, y); }

    int findCircleNum(vector<vector<int>>& isConnected) {
        int n = isConnected.size();
        int m = isConnected[0].size();
        vector<int> parent(n);
        for (int i = 0; i < n; i++)
            parent[i] = i;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < m; j++) {
                if (isConnected[i][j])
                    Union(parent, i, j);
            }
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {
            if (parent[i] == i)
                ans++;
        }
        return ans;
    }
};

复杂度分析

时间复杂度:\(O(n^2logn)\),其中 n 是城市的数量。需要遍历矩阵 isConnected 中的所有元素,时间复杂度是 \(O(n^2)\),如果遇到相连关系,则需要进行 2 次查找和最多 1 次合并,一共需要进行 \(2n^2\)次查找和最多\(n^2\)次合并,因此总时间复杂度是$ O(2n^2logn^2 )=O(n^2logn)\(。这里的并查集使用了路径压缩,但是没有使用按秩合并,最坏情况下的时间复杂度是 \(O(n^2logn)\),平均情况下的时间复杂度依然是 \(O(n2α(n))\),其中 α 为阿克曼函数的反函数,\)α(n) $可以认为是一个很小的常数。

空间复杂度:\(O(n)\),其中 n 是城市的数量。需要使用数组 parent 记录每个城市所属的连通分量的祖先。