题目来源

• leetcode：323. 无向图中连通分量的数目

题目描述

注意:
你可以假设在 edges 中不会出现重复的边。而且由于所以的边都是无向边，[0, 1] 与 [1, 0] 相同，所以它们不会同时在 edges 中出现。

class Solution {
    
public:
    int countComponents(int n, vector<pair<int, int> >& edges){
    
        
    }
};

题目解析

图

思路：

• 先构建邻接表
• 然后DFS：
  • 给每个节点都有个flag标记其是否被访问过
  • 如果出现了一个未被访问过的节点，那么++ans，然后通过邻接表遍历所有相邻的节点，并将它们标记为访问过
  • 遍历完所有的连通节点后我们继续寻找下一个未访问过的节点，以此类推直至所有的节点都被访问过了
  • 最终ans就是联通区域的个数

class Solution {
    
    void dfs(std::vector<std::vector<int>> &g, std::vector<bool> &v, int i){
    
        v[i] = true;
        for (int j = 0; j < g[i].size(); ++j) {
    
            if(v[g[i][j]] == false){
    
                dfs(g, v, g[i][j]);
            }
        }
    }
public:
    int countComponents(int n, vector<pair<int, int> >& edges){
    

        std::vector<std::vector<int>> g;
        g.resize(n);
        // 1、采用邻接表构建无向连通图
        for(auto a : edges){
    
            g[a.first].push_back(a.second);
            g[a.second].push_back(a.first);
        }

        // 2、采用BFS获取连通分量个数
        int ans = 0;
        std::vector<bool> v(n, false);
        for (int i = 0; i < n; ++i) {
    
            if(v[i] == false){
    
                dfs(g, v, i);
                ++ans;
            }
        }
        return ans;
    }
};

并查集

class Solution {
    
    class UnionFind{
    
        int cnt;
        std::vector<int> parents;

        int findRoot(int i){
    
            int root = i;
            while (parents[root] != root){
    
                root = parents[root];
            }
            return root;
        }
    public:
        UnionFind(int n){
    
            cnt = n;  // 初始时所有顶点都指向自己,连通分量数为节点数
            parents.resize(cnt);

            for (int i = 0; i < cnt; ++i) {
    
                parents[i] = i;  // 初始时所有节点都指向自己
            }
        }

        int getConnected(){
    
            return cnt;
        }


        void merge(int i, int j){
    
            int p1 = findRoot(i);
            int p2= findRoot(j);
            if(p1 == p2){
    
                return;
            }

            parents[p1] = p2;
            --cnt;
        }


    };
public:
    int countComponents(int n, vector<pair<int, int> >& edges){
    
        UnionFind u(n);
        // 遍历邻接表(边)合并连通节点
        for (int i = 0; i < edges.size(); ++i) {
    
            u.merge(edges[i].first, edges[i].second);
        }

        return u.getConnected();
    }
};

类似题目

• LeetCode 133. Clone Graph 克隆无向图
• LeetCode 310. Minimum Height Trees（最小高度树）
• LeetCode 207. Course Schedule 课程清单