[S2] 11724. 연결 요소의 개수

https://www.acmicpc.net/problem/11724

11724번: 연결 요소의 개수

2가지 방법이 존재한다. 모든 그래프가 그렇듯이 dfs 또는 노드의 연결(노드의 parent를 저장하여 parent를 방문하는 것이다.)

 

방법 1. bfs 또는 dfs

나는 bfs방식으로 해결하였다. 우선 전부 입력을 받고 그 값을 vector또는 bool배열에 저장한다. 나는 vector로 저장하였다. 그리고, 차례로 방문하여 해당 수의 visited를 설정한다. bfs를 통해 queue가 다 비워졌다면 방문했던 모든 노드는 하나의 연결 요소가 된다. 다음 연결 요소를 찾기 위해서는 visited가 false로 되어 있는 요소를 찾아가는 것이다. 그렇게 하여 총 연결 요소의 개수를 구할 수 있게 된다. 하지만 이 방법보다 더 효율적인 방법이 존재한다.

#include <cstdio>
#include <queue>
#include <vector>

int main(void) {
    int N, M, u, v, R = 0; scanf("%d %d", &N, &M);
    bool V[1001]{};
    std::vector<int> vec[1001];

    while (M--) {
        scanf("%d %d", &u, &v);
        vec[u].push_back(v);
        vec[v].push_back(u);
    }

    for (int i = 1; i <= N; i++) {
        if (V[i]) continue;
        V[i] = true;
        std::queue<int> q;
        q.push(i);
        while (!q.empty()) {
            for (auto j : vec[q.front()]) {
                if (V[j]) continue;
                q.push(j);
                V[j] = true;
            }
            q.pop();
        }
        R++;
    }
    printf("%d", R);
}

 

방법 2. parent노드 저장.

하나의 배열을 선언하고, 해당 배열에는 그 노드의 부모 노드를 저장하는 것이다. 부모 노드의 부모 노드가 존재한다면 해당 노드의 부모 노드를 부노 노드의 부모노드로 변경해주고, 그러다가 부모 노드가 동일하다면 연결 요소의 개수를 1개 빼주는 것이다. 

find함수 - 부모 노드를 리턴해주는 함수이다. 하지만, 해당 노드의 부모 노드가 계속해서 연결되어 있다면 해당 노드의 부모 노드도 변경해주기 위해 재귀 함수 형식으로 사용한다.

 

Union함수 - 만약 부모 노드가 다르다면 다른 연결 요소끼리 합쳐지는 것이기 때문에 연결 요소의 개수를 1 빼주고, 부모 노드를 통합해 준다.

만약 부모 노드가 같다면 이미 연결 요소 처리가 된 것이기 때문에 아무것도 하지 않는다.

#include <cstdio>

int node[1001], R, N;

int find(int a) {
    return a == node[a] ? a : node[a] = find(node[a]);
}

void Union(int a, int b) {
    int PA = find(a);
    int PB = find(b);
    if (PA != PB) {
        node[PB] = find(PA);
        N--;
    }
}

int main(void) {
    int M, u, v; scanf("%d %d", &N, &M);

    for (int i = 1; i <= N; i++) node[i] = i;
    for (int i = 0; i < M; i++) {
        scanf("%d %d", &u, &v);
        Union(u, v);
    }
    printf("%d", N);
}