323. Number of Connected Components in an Undirected Graph - cocoder39/coco39_LC GitHub Wiki

class Solution:
    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        graph = {}
        for i in range(n):
            graph[i] = []
            
        for a, b in edges:
            graph[a].append(b)
            graph[b].append(a)
        
        groups = {}
        cur_group_id = 0
        for k, v in graph.items():
            if k not in groups:
                cur_group_id += 1
                groups[k] = cur_group_id
                queue = collections.deque([k])
                while queue:
                    sz = len(queue)
                    for i in range(sz):
                        cur_node = queue.pop()
                        for next_node in graph[cur_node]:
                            if next_node not in groups:
                                groups[next_node] = cur_group_id
                                queue.append(next_node)
        return cur_group_id

class Solution {
public:
    int countComponents(int n, vector<pair<int, int>>& edges) {
        UnionFind uf(n);
        for (auto edge : edges) 
            uf.makeUnion(edge.first, edge.second);
        return uf.getCnt();
    }
private:
    class UnionFind {
    public:    
        UnionFind(int n) {
            cnt = n;
            for (int i = 0; i < n; i++) {
                id.push_back(i);
                sz.push_back(1);
            }
        }   

        bool isUnion(int p, int q) {
            return root(p) == root(q);
        }
        
        void makeUnion(int p, int q) {
            int i = root(p);
            int j = root(q);
            if (i == j) return;
            
            if (sz[i] < sz[j]) {
                id[i] = j;
                sz[j] += sz[i];
            }
            else {
                id[j] = i;
                sz[i] += sz[j];
            }
            cnt--;
        }
        
        int getCnt() {
            return cnt;
        }
    private:
        int cnt;
        vector<int> id;
        vector<int> sz;
        
        int root(int i) {
            while (i != id[i]) {
                id[i] = id[id[i]];
                i = id[i];
            }
            return i;
        }
    };
};