백준 #11724 연결 요소의 개수

백준 #11724 연결 요소의 개수

연결 요소의 개수를 구하는 문제.

BFS 또는 DFS로 구할 수 있다. DFS로 풀었다.

#include <iostream>
#include <cstring>
#include <vector>
#include <bits/stdc++.h>

using namespace std;
int N, M;
vector<int> graph[1001];
bool visited[1001];
int totalCount;

void dfs(int start) {
    visited[start] = true;
    for(int i = 0; i < graph[start].size(); i++) {
        int next = graph[start][i];
        if(!visited[next]) {
            dfs(next);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N >> M;
    totalCount = 0;
    memset(visited, 0, sizeof(visited));
    for(int i = 0; i < M; i++) {
        int from, to;
        cin >> from >> to;
        graph[from].push_back(to);
        graph[to].push_back(from);
    }
    for(int i = 1; i <= N; i++) {
        if(!visited[i]) {
            totalCount++;
            dfs(i);
        }
    }
    cout << totalCount;

    return 0;
}

Disjoint set으로 풀 수도 있다. 이 경우가 더 빠르다.

#include <iostream>
#include <vector>
#include <unordered_set>

using namespace std;

int findRoot(vector<int> &parent, int u) {
    if (u == parent[u]) {
        return u;
    }
    return parent[u] = findRoot(parent, parent[u]);
}

void merge(vector<int> &parent, vector<int> &level, int u, int v) {
    u = findRoot(parent, u);
    v = findRoot(parent, v);
    if (u == v) {
        return;
    }
    if (level[u] < level[v]) {
        parent[u] = v;
    } else if (level[u] > level[v]) {
        parent[v] = u;
    } else {
        parent[u] = v;
        level[v]++;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int N, M;
    cin >> N >> M;
    vector<int> parent(N + 1);
    vector<int> level(N + 1, 1);
    for (int i = 1; i <= N; i++) {
        parent[i] = i;
    }
    for (int i = 0; i < M; i++) {
        int from, to;
        cin >> from >> to;
        merge(parent, level, from, to);
    }
    unordered_set<int> roots;
    for (int i = 1; i <= N; i++) {
        roots.insert(findRoot(parent, i));
    }
    cout << roots.size();
    return 0;
}