323. Number of Connected Components in an Undirected Graph

題目網址：https://leetcode.cn/problems/number-of-connected-components-in-an-undirected-graph/

題意：有一含 n 個 node 的 graph, 給你一整數 n 和 edges, 其中 edges[i] = [a, b] 代表 graph 中 a 和 b 之間有一邊, 返回 connected component 個數。

Solution 1：

想法：利用 DFS, 依序對所有 node 做 dfs, 每次判斷該 node 是否被拜訪過, 若還沒代表有新的 component

e.g. n = 5, edges = [[0, 1], [1, 2], [3, 4]]

• 先對 0 做 dfs 得到第一個 component(0,1,2), 同時 visited[0,1,2] 都被設為 true

• 因為 visited[3] = false, 所以對 3 做 dfs 得到第二個 component(3,4)

  

class Solution {
public:
    int countComponents(int n, vector<vector<int>>& edges) {
        vector<vector<int>> adj(n);
        vector<bool> visited(n, false);

        for (const auto& e : edges) {
            adj[e[0]].emplace_back(e[1]);
            adj[e[1]].emplace_back(e[0]);
        }

        int res = 0;
        for (int i = 0; i < n; ++i) {
            if (!visited[i]) {
                ++res;
                dfs(adj, visited, i);
            }
        }
        return res;
    }

private:
    void dfs(vector<vector<int>>& adj, vector<bool>& visited, int& cur){
        visited[cur] = true;

        for (const auto& v : adj[cur]) {
            if (!visited[v]) {
                dfs(adj, visited, v);
            }
        }
    }
};

• time：$O(V+E)$ ➔ 必須拜訪所有 node, 和其延伸出去的所有 edge
  • V 是 node 數, E 是 edge 數
• space：$O(V+E)$ ➔ 因為 adj 為 $O(V+E)$, V 是因為要記錄所有點, E 是因為會記錄所有邊

Solution 2：

想法：利用 BFS, 道理同 DFS, 依序對所有 node 做 bfs, 每次判斷該 node 是否被拜訪過, 若還沒代表有新的 component

class Solution {
public:
    int countComponents(int n, vector<vector<int>>& edges) {
        vector<int> visited(n, false);
        vector<vector<int>> adj(n);

        for (const auto& e : edges) {
            adj[e[0]].emplace_back(e[1]);
            adj[e[1]].emplace_back(e[0]);
        }

        int res = 0;
        for (int i = 0; i < n; ++i) {
            if (!visited[i]) {
                ++res;
                bfs(adj, visited, i);
            }
        }
        return res;
    }

private:
    void bfs(vector<vector<int>>& adj, vector<int>& visited, int& i){
        queue<int> q({i});

        while (!q.empty()) {
            for (int k = q.size(); k > 0; --k) {
                const auto cur = q.front();
                q.pop();
                visited[cur] = true; // 將 cur 設為已拜訪

                for (const auto& v : adj[cur]) {
                    if (!visited[v]) {
                        q.emplace(v); // 將未拜訪的相鄰點加到 queue 中
                    }
                }
            }
        }
    }
};

• time：$O(V+E)$ ➔ 必須拜訪所有 node, 和其延伸出去的所有 edge
  • V 是 node 數, E 是 edge 數
• space：$O(V+E)$ ➔ adj

Solution 3：

想法：利用 Union Find + Path Compression

class Solution {
public:
    int countComponents(const int n, vector<vector<int>>& edges) {
        vector<int> parents(n, 0); // 紀錄每個點的 parent
        vector<int> ranks(n, 1); // 紀錄每個點的 rank

        // 每個點的 parent 都初始成自己
        for (int i = 0; i < n; ++i) {
            parents[i] = i;
        }

        res = n; // 一開始令每個 node 都自己一個 set, 然後才開始合併
        for (const auto& e : edges) {
            const int r1 = find(parents, e[0]); // root of a
            const int r2 = find(parents, e[1]); // root of b

            // 如果 a, b 是同個 set, 則不做任何事
            if (r1 == r2) {
                continue;
            }

            // a, b 是不同 set, 則兩個 set 合併成一個 set
            union_(parents, ranks, r1, r2);
        }
        return res;
    }

private:
    int res;

    void union_(vector<int>& parents, vector<int>& ranks, const int r1, const int r2){
        // 深度低的 tree root 把深度高的 tree root 作為 parent
        if (ranks[r1] > ranks[r2]) {
            parents[r2] = r1;
        } else if (ranks[r1] < ranks[r2]) {
            parents[r1] = r2;
        } else { // 若深度一樣, 可以任意選擇一個 root 作為 parent
            parents[r2] = r1;
            ++ranks[r1]; // 作為 parent 的 node 之 rank 值會加一, 因為深度變了
        }
        --res; // 合併後, set 數 - 1
    }

    int find(vector<int>& parents, int i){
        while (i != parents[i]) {
            parents[i] = parents[parents[i]]; // path compression
            i = parents[i];
        }
        return i;
    }
};

• time：$O(V+E)$ ➔ 遍歷每個 node 初始化 parents, 以及遍歷每條 edge 做 union find, 其中 edge 的兩端點做 find() 皆只需 $O(1)$
• space：$O(n)$ ➔ parents , ranks