Leetcode - 323. Number of Connected Components in an Undirected Graph

문제

주어진 그래프에서 서로 연결된 그룹의 갯수는?

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

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

해결 아이디어

• union find를 수행하고, 각 노드에 find()를 수행하면 대표노드를 얻을 수 있다. 같은 그룹에 있는 노드의 대표노드는 반드시 같기 때문에, 서로 다른 대표노드의 갯수를 구하면 된다.
• 해시테이블을 사용해 O(n)으로 대표노드의 갯수를 구한다.

풀이

class Solution {
public:
    vector<int> parent;
    int find(int n) {
        if (parent[n] == n)
            return n;
        return find(parent[n]);
    }
    void do_union(int a, int b) {
        int roota = find(a);
        int rootb = find(b);
        parent[roota] = rootb;
    }
    int countComponents(int n, vector<vector<int>>& edges) {
        parent = vector<int>(n);
        int comp = 0;
        unordered_map<int, int> freq;
        
        for (int i = 0; i < n; i++)
            parent[i] = i;
        for (auto it: edges)
            do_union(it[0], it[1]);
        
        int root = 0;
        for (int i = 0; i < n; i++) {
            root = find(i);
            if (freq.find(root) == freq.end()) {
                comp++;
                freq[root] = 1;
            }
        }
        return comp;
    }
};