323

323. Number of Connected Components in an Undirected Graph (Medium)

You have a graph of n nodes. You are given an integer n and an array edges where edges[i] = [ai, bi] indicates that there is an edge between ai and bi in the graph.

Return the number of connected components in the graph.

 

Example 1:

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

Example 2:

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

 

Constraints:

• 1 <= n <= 2000
• 1 <= edges.length <= 5000
• edges[i].length == 2
• 0 <= ai <= bi < n
• ai != bi
• There are no repeated edges.

Companies:
Amazon, Facebook, Microsoft, LinkedIn, Apple

Related Topics:
Depth-first Search, Breadth-first Search, Union Find, Graph

Similar Questions:

• Number of Islands (Medium)
• Graph Valid Tree (Medium)
• Number of Provinces (Medium)

Solution 1. Union Find

// OJ: https://leetcode.com/problems/number-of-connected-components-in-an-undirected-graph/
// Author: github.com/lzl124631x
// Time: O(E + N)
// Space: O(N)
class UnionFind {
    vector<int> id;
    int cnt;
public:
    UnionFind(int n) : cnt(n), id(n) {
        iota(begin(id), end(id), 0);
    }
    int find(int a) {
        return id[a] == a ? a : (id[a] = find(id[a]));
    }
    void connect(int a, int b) {
        int p = find(a), q = find(b);
        if (p == q) return;
        id[p] = q;
        --cnt;
    }
    int getCount() {
        return cnt;
    }
};
class Solution {
public:
    int countComponents(int n, vector<vector<int>>& E) {
        UnionFind uf(n);
        for (auto &e : E) {
            uf.connect(e[0], e[1]);
        }
        return uf.getCount();
    }
};