백준 11724번: 연결 요소의 개수 (C++)

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

DFS를 활용해서 연결 요소의 개수를 파악해준다. 연결된 클러스터의 개수를 파악하는 문제라고 생각하면 된다.

DFS가 몇번 실행되는지 파악해주면되고, 무방향 그래프라는 것을 인지하고 인접행렬의 형태로 입력을 받아준다.

#pragma warning(disable :4996)
#include<iostream>
using namespace std;
 
int grp[1001][1001], n, m; //1-indexed
bool vis[1001];
 
void dfs(int cur) {
    for (int i = 1; i <= n; i++) {
        if (grp[cur][i] == 1 && !vis[i]) {
            vis[i] = true;
            dfs(i);
        }
    }
}
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n >> m;
 
    for (int i = 1; i <= m; i++) {
        int src, dst;
        cin >> src >> dst;
        grp[src][dst] = 1;
        grp[dst][src] = 1; //방향이 없으므로
    }
 
    int ret = 0;
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            //printf("%d에서 실행\n", i);
            vis[i] = true;
            dfs(i);
            ret++; //dfs의 실행 횟수가 곧 연결 요소의 수
        }
    }
 
    cout << ret;
    return 0;
}