[백준/11724/C] 연결 요소의 개수

바이러스 문제와 같은 방식으로 DFS를 쓰면 쉽게 풀리는 문제이다.

(특이 케이스만 아니면 BFS보다는 DFS가 너무 편하다..)

#include <stdio.h>
#include <stdlib.h>

int Graph[1001][1001];
int visited[1001];
int N,M,cnt = 0;

void dfs(int i){
    visited[i]=1;
    for(int j=1; j<=N; j++){
        if(!visited[j] && Graph[i][j]){
            visited[j]=1;
            dfs(j); 
        }
    }
}

int main(){
    scanf("%d %d",&N,&M);int p,q;
    for(int i=0; i<M; i++){ 
        scanf("%d %d",&p,&q);
        Graph[p][q]++; Graph[q][p]++;
    }
    for(int i=1; i<N+1; i++){
        visited[i]=0;
    }
    for(int i =1; i<=N; i++){
        if (!visited[i]) {
            dfs(i); cnt++;
        }
    }
    printf("%d",cnt);
}