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

문제

문제 바로가기> 백준 11724번: 연결 요소의 개수

풀이

dfs를 이용하여 간단하게 문제를 풀 수 있다. 연결 요소(= 연결 그래프) 개수를 구하기 위해 main에서 반복문을 돌면서 연결되어 있지 않아서 방문하지 못하는 정점도 방문하도록 해주었다. 예를 들어 예제 입력 1 같은 경우 1, 2, 5가 연결 되어 있고 3, 4, 6이 연결되어 있는데, 처음 dfs(1)을 호출하면 1, 2, 5를 방문하게 된다. 이후 main에서 정점 2는 방문했으므로 dfs(3)을 호출하고 연결된 3, 4, 5를 방문하여 모든 정점을 방문한다.

#include <iostream>
using namespace std;

int arr[1001][1001]={};
int visit[1001]={};
int n, m; 

void dfs(int num){
    visit[num]=1;
    for(int i=1; i<=n; i++){
        if(!visit[i] && arr[num][i]) dfs(i);
    }
}

int main(){
    int a, b, ans=0; cin>>n>>m;
    for(int i=0; i<m; i++){
        cin>>a>>b;
        arr[a][b]=1; arr[b][a]=1;  
    }
    for(int i=1; i<=n; i++){
        if(!visit[i]) {
            ans++;
            dfs(i);
        }
    }
    cout<<ans;
}