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.

class Solution {

public:

    int countComponents(int n, vector<vector<int>>& edges) {

        if (n == 0) {

            return 0;

        }

        

        vector<bool> visited(n, false);

        map<int, set<int>> graph;

        for (int i = 0; i < n; i++) {

            graph[i] = {};

        }

        

        for (auto edge : edges) {

            graph[edge[0]].insert(edge[1]);

            graph[edge[1]].insert(edge[0]);

        }

        

        int counter = 0;

        

        for (auto entry : graph) {

            if (!visited[entry.first]) {

                counter++;

                dfs(entry.first, graph, visited);

            }

        }

        return counter;

    }

    

    void dfs(int node, map<int, set<int>>& graph, vector<bool>& visited) {

        if (visited[node]) {

            return;

        }

        visited[node] = true;

        for (auto neighbor : graph[node]) {

            if (!visited[neighbor]) {

                dfs(neighbor, graph, visited);

            }

        }

    }

};

======== disjoint set ====

int countComponents(int n, vector<vector<int>>& edges) { vector<int> parent(n); int cnt = n; for (int i = 0; i < n; i++) parent[i] = i; for (const auto& edge : edges) { int w = edge[0], v = edge[1]; while (parent[w] != w) w = parent[w] = parent[parent[w]]; while (parent[v] != v) v = parent[v] = parent[parent[v]]; if (w != v) { parent[w] = v; cnt--; } } return cnt; }