[ leetcode 문제풀이 ] Number of Connected Components in an Undirected Graph

Number of Connected Components in an Undirected Graph - LeetCode

Account Login - LeetCode

(Number of Connected Components in an Undirected Graph는 LeetCode Premium 문제로 위 링크 혹은 LintCode를 통해 풀어보실 수 있습니다.)

 

 

 

< Number of Connected Components in an Undirected Graph 문제 설명 >

 

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.

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.

 

0에서 n-1로 이름 붙여진 n개의 nodes와 무방향 간선의 배열이 주어질 때 무방향 그래프에서 connected components의 수를 찾는 함수를 작성하여라.

 

다음 두 가지 출력 예시가 주어졌다.

 

 

 

 

 

---

< Number of Connected Components in an Undirected Graph 문제 접근 >

 

Graph를 탐색하는 DFS나 BFS로도 이 문제를 풀 수 있겠지만, 주어진 edges로 0 ~ n-1 node를 partition하는 개념으로 생각할 수 있으므로 Union-Find data structure을 사용하고자 하였다. 작성한 코드를 먼저 보면 다음과 같다. (Cpp 사용)

 

#include <algorithm>

struct Node{
    vector<int> parent;
    vector<int> rank;
    Node(int n) : parent(n), rank(n,0){
        for(int i=0;i<n;i++) parent[i] = i;
    }
    // this can be decreased to a constant amount memory
    // by performing both passes in the same direction
    // two passes - once to find the root, once to update pointers.
    int Find(int x){
        int root = x;
        while(parent[root] != root)
            root = parent[root];
            
        while(parent[x] != root){
            int temp = parent[x];
            parent[x] = root;
            x = temp;
        }
        return root;            
    }   
    // union by rank - ensure that trees do not become too deep
    void Union(int x, int y, int& count){
        x = Find(x);
        y = Find(y);
         
        if(x == y) return;

        if(rank[x] < rank[y])
            swap(x,y);
            
        parent[y] = x;
        if(rank[x] == rank[y])
            rank[x]++;
            
        count--;
    }
};
int countComponents(int n, vector<vector<int>> edges) {
    Node Vertices(n);

    int count = n;
    for(auto edge : edges)
         Vertices.Union(edge[0], edge[1], count);
        
    return count;
}

 

count라는 int 변수로 connected component의 개수를 세고자 하였는데, count는 당시 시점에서의 connected component의 수이다. 즉, 초기 상태에서는 모든 node가 연결되어 있지 않은 상태이므로 count를 n으로 초기화하고(엄밀히 말해서 vertex만 있는 경우는 connected 된 상태라고 할 수 없지만 edges를 순회하며 연결을 진행할 예정이므로 편의상 이렇게 작성한다.) union operation이 진행되는 경우 connected component의 생성 혹은 두 connected components의 merge가 일어난 것이므로 count를 1만큼 줄인다.

 

이 과정으로 전체 edge에 대해 union을 실시해 나오는 count가 바로 connected components의 수가 되는 것이다.