11724번: 연결 요소의 개수

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

11724번: 연결 요소의 개수

입력으로 주어진 그래프의 개수를 세는 문제이므로, 그래프를 그대로 저장한 뒤 그래프를 탐색해 그래프의 개수를 출력하거나, 그래프에 크루스칼 기법을 적용한 뒤 만들어진 트리의 루트 노드의 개수를 출력하면 된다.

- 그래프 탐색

#include <iostream>

using namespace std;

#define MAX_N 1000

// graph[i][j]: 노드 i와 노드 j를 잇는 에지가 존재한다면 true
bool graph[MAX_N][MAX_N];
// 노드의 개수
int N;

// 노드 node와 연결된 각 노드를 dfs
void dfs(int node) {
    // 현재 노드를 탐색함을 표시한 뒤
    graph[node][node] = false;

    // 현재 노드와 연결되어 있고 미탐색한 노드가 있다면
    for (int i = 0; i < N; i++) if (graph[i][i] && graph[node][i]) {
        // 연결을 해제한 뒤 노드 i를 탐색
        graph[node][i] = graph[i][node] = false;
        dfs(i);
    }
}

int main() {
    // 입출력 속도 향상
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    // M: 에지의 개수, a, b: 에지가 잇는 두 노드, ans: 연결 요소의 개수
    int M, a, b, ans = 0;

    // 노드의 개수와 에지의 개수를 입력받은 뒤 각 에지에 대해
    for (cin >> N >> M; M--;) {
        // 에지를 입력받아 graph에 저장
        cin >> a >> b;
        graph[a][b] = graph[--b][--a] = true;
    }
    // i번 노드에서 i번 노드로 이동하는 에지는 없으므로
    // graph[i][i]를 visit처럼 사용
    for (int i = 0; i < N; i++) graph[i][i] = true;

    // 모든 노드를 방문하면서 그래프의 개수를 계산
    for (int i = 0; i < N; i++) if (graph[i][i]) {
        dfs(i);
        ans++;
    }

    // 그래프의 개수를 출력
    cout << ans << '\n';

    return 0;
}

 

- 크루스칼 기법

#include <iostream>

using namespace std;

#define MAX_N 1000

// parent[i]: 노드 i의 부모 노드
int parent[MAX_N + 1];

// 노드 node가 속한 트리의 루트 노드를 재귀적으로 탐색
int root(int node) {
    if (parent[node] && parent[node] != node)
        return parent[node] = root(parent[node]);
    return parent[node] = node;
}

int main() {
    // 입출력 속도 향상
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    // visit[i]: 루트 노드가 i인 그래프를 탐색했다면 true
    bool visit[MAX_N + 1] = { 0, };
    // N: 노드의 수, M: 에지의 수, a, b: 각 에지를 이루는 두 노드, ans: 그래프의 수
    int N, M, a, b, ans = 0;

    // 노드와 에지의 수를 입력받은 뒤 각 에지에 대해
    for (cin >> N >> M; M--; ) {
        // 에지를 이루는 두 노드를 입력받고
        cin >> a >> b;

        // 두 노드가 속한 트리의 루트 노드를 계산한 뒤
        a = root(a);
        b = root(b);
        // 두 트리를 연결
        parent[a] = b;
    }

    // 각 노드가 속한 트리의 루트 노드만을 방문한 뒤
    for (int i = 1; i <= N; i++) visit[root(i)] = true;
    // 루트 노드의 개수를 계산해 ans에 저장
    for (int i = 1; i <= N; i++) ans += visit[i];

    // 루트 노드의 개수, 즉 연결 요소의 개수를 출력
    cout << ans << '\n';
    
    return 0;
}