[백준]11724번

union_find structure로 해결하는 문제다

#include <iostream>
#include <vector>

std::vector<int> parent;

int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]);  // path compression
    }
    return parent[x];
}

void unite(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);
    if (rootX != rootY) {
        parent[rootY] = rootX;
    }
}

int main() {
    int n, m;
    std::cin >> n >> m;

    parent.resize(n);
    for (int i = 0; i < n; i++) {
        parent[i] = i;  // 각 노드의 부모를 자기 자신으로 초기화
    }

    for (int i = 0; i < m; i++) {
        int x, y;
        std::cin >> x >> y;
        unite(x-1, y-1);  // 1-indexed를 0-indexed로 변환
    }

    std::vector<bool> isRoot(n, false);
    for (int i = 0; i < n; i++) {
        isRoot[find(i)] = true;
    }

    int count = 0;
    for (int i = 0; i < n; i++) {
        if (isRoot[i]) {
            count++;
        }
    }

    std::cout << count << std::endl;

    return 0;
}