323. Number of Connected Components in an Undirected Graph

Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to find the number of connected components in an undirected graph.

Example 1:

Input: n = 5 and edges = [[0, 1], [1, 2], [3, 4]]

     0          3
     |          |
     1 --- 2    4 

Output: 2

Example 2:

Input: n = 5 and edges = [[0, 1], [1, 2], [2, 3], [3, 4]]

     0           4
     |           |
     1 --- 2 --- 3

Output:  1

Note: You can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.

建立roots array 來代表i屬於group roots[i]，利用union-find來合併edge上兩端的節點，若edge上兩個節點所屬的group不同，那就將他們合併為同一個group，每合併一次就減少總group數量。

// Union Find
int getRoot(vector<int>& roots, int i) {
    return roots[i] == i ? i : roots[i] = getRoot(roots, roots[i]);
}
int countComponents(int n, vector<vector<int>>& edges) { // time: O(E * log*(n)); space: O(n)
    int res = n;
    vector<int> roots(n), size(n, 1);
    for (int i = 0; i < n; ++i) roots[i] = i;
    for (auto edge : edges) {
        int r1 = getRoot(roots, edge[0]);
        int r2 = getRoot(roots, edge[1]);
        if (r1 != r2) {
            if (size[r1] >= size[r2]) {
                roots[r2] = r1;
                size[r1] += size[r2];
            } else {
                roots[r1] = r2;
                size[r2] += size[r1];
            }
            --res;
        }
    }
    return res;
}

根據edges建立adjacency list，DFS搭配visited array來記錄是否已經掃描過該節點。

// DFS + adjacency list
void dfs(vector<vector<int> >& graph, vector<bool>& visited, int i) {
    if (visited[i]) return;
    visited[i] = true;
    for (int j = 0; j < graph[i].size(); ++j) {
        dfs(graph, visited, graph[i][j]);
    }
}
int countComponents(int n, vector<vector<int>>& edges) { // time: O(n + E); space: (n + E)
    int res = 0;
    vector<vector<int> > graph(n); // adjacency list
    vector<bool> visited(n, false);
    // build graph
    for (vector<int>& edge : edges) {
        graph[edge[0]].push_back(edge[1]);
        graph[edge[1]].push_back(edge[0]);
    }
    // DFS
    for (int i = 0; i < n; ++i) {
        if (!visited[i]) {
            dfs(graph, visited, i);
            ++res;
        }
    }
    return res;
}

根據edges建立adjacency list，BFS搭配visited array來紀錄是否已經掃描過該節點。

// BFS + adjacency list
int countComponents(int n, vector<vector<int>>& edges) { // time: O(E + n); space: O(E + n)
    vector<vector<int> > graph(n); // adjacency list
    vector<bool> visited(n, false);
    // build graph
    for (vector<int>& edge : edges) { // time: O(E)
        graph[edge[0]].push_back(edge[1]);
        graph[edge[1]].push_back(edge[0]);
    }
    int res = 0;
    // BFS
    for (int i = 0; i < n; ++i) { // time: O(n)
        if (!visited[i]) {
            ++res;
            queue<int> q({i});
            while (!q.empty()) {
                int index = q.front(); q.pop();
                visited[index] = true;
                for (int neighbor : graph[index]) {
                    if (!visited[neighbor]) q.push(neighbor);
                }
            }
        }
    }
    return res;
}