Number of Connected Components in an Undirected Graph

Problem

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

Return the number of connected components in the graph.

Examples

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 <= aᵢ <= bᵢ < n
• aᵢ != bᵢ
• There are no repeated edges.

You should aim for a solution as good or better than O(V + E) time and O(V + E) space, where V is the number vertices and E is the number of edges in the graph.

Solution

Start with an unvisited node, increment the component counter, then run BFS removing those nodes from consideration.

class Solution {
public:
    int countComponents(int n, vector<vector<int>>& edges) {
        // Make graph
        std::vector<std::unordered_set<int>> adj(n);
        for (const auto &e : edges) {
            adj[e[0]].insert(e[1]);
            adj[e[1]].insert(e[0]);
        }
 
        std::unordered_set<int> unvisited_nodes;
        unvisited_nodes.reserve(n);
        for (int i = 0; i < n; ++i) {
            unvisited_nodes.insert(i);
        }
 
        int components = 0;
        std::queue<int> open;
        while (!unvisited_nodes.empty()) {
            int start_node = *unvisited_nodes.begin();
            unvisited_nodes.erase(start_node);
            ++components;
            open.push(start_node);
            while(!open.empty()) {
                int node = open.front();
                open.pop();
                for (const auto &n : adj[node]) {
                    if (unvisited_nodes.contains(n)) {
                        open.push(n);
                        unvisited_nodes.erase(n);
                    }
                }
            }
        }
        return components;
    }
};