323. Number of Connected Components in an Undirected Graph

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.

c++

class Solution {
    unordered_map<int, int> g;
    int getRoot(int n) {
        return g[n] == n ? n : getRoot(g[n]);
    }
    void setRoot(int n, int root) {
        if(g[n] == root) return;
        if(g[n] == n) g[n] = root;
        setRoot(g[n], root);
        g[n] = root;
    }
public:
    int countComponents(int n, vector<vector<int>>& edges) {
        for(int i = 0; i < n; i ++) g[i] = i;
        for(auto& e : edges) {
            int r1(getRoot(e.front())), r2(getRoot(e.back()));
            if(r1 == r2) continue;
            setRoot(e.front(), min(r1, r2));
            setRoot(e.back(), min(r1, r2));
            n--;
        }
        
        return n;
    }
};