11724번: 연결 요소의 개수

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


$O(n^2)$

#include<cstdio>
int n, m, ck[1001], r, adj[1001][1001];
void dfs(int h) {
    ck[h] = 1;
    for (int i = 1; i <= n; i++) if (adj[h][i] && !ck[i]) dfs(i);
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0, x, y; i < m; i++) {
        scanf("%d%d", &x, &y);
        adj[x][y] = adj[y][x] = 1;
    }
    for (int i = 1; i <= n; i++) if (!ck[i]) dfs(i), r++;
    printf("%d", r);
    return 0;
}