백준 11724번:연결 요소의 갯수

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

이번 문제는 제가 포스팅한 DFS를 참고하면 좋을 거 같아요. (http://tiger1710.tistory.com/7)

이 문제는 탐색을 하면서 dfs 함수가 탐색한 횟수만 체크해주면 될거 같아요.

제가 공부한 dfs코드와 거의 변함이 없어서..

#include <stdio.h>
#include <stdbool.h>
#define MAX 1001
 
int G[MAX][MAX];
bool visited[MAX];
int N, M;
int cnt;
 
void dfs(int k) {
    visited[k] = true;
    for (int i = 1; i <= N; i++) {
        if (visited[i] != false || G[k][i] == 0) continue;
        dfs(i);
    }
}
 
int main(void) {
 
    scanf("%d%d", &N,&M);
 
    for (int i = 0; i < M; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        G[u][v] = 1;
        G[v][u] = 1;
    }
    
    for (int i = 1; i <= N; i++) {
        if (!visited[i]) {
            dfs(i);
            cnt++;
        }
    }
    
    printf("%d\n", cnt);
 
 
    return 0;
}

5~8:모든 변수를 전역변수로 정의했습니다.(0으로 초기화 하기위해)

29~34:간선의 갯수만큼 dfs함수를 호출해 줍니다.

30:이미 방문했다면 dfs함수를 호출하지 않고

32:한번 호출할때마다 갯수를 하나씩 올렸습니다.