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

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

1. 문제

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

2. 알고리즘

키워드 - DFS

[ Figure 1 ]

1번 TestCase 는 연결 요소가 두 개다.

[ Figure 2 ]

2 번 TestCase 에서는 모든 정점이 연결되어 있어 연결 요소는 하나다.

3. 코드

#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <stack>
#include <cstring>
 
#define MAX_SIZE 100
#define INF 0x7fffffff
 
using namespace std;
 
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, -1, 1};
 
int reverse(int x) {
    int rev = 0;
    while(x != 0){
        rev = rev*10 + x%10;
        x = x/10;
    }
    return rev;
}
 
// 전역으로 선언하면 0 으로 초기화 된다.
int board[1001][1001];
int visited[1001];
 
int n,m;
void dfs(int position) {
    visited[position] = 1;
 
    for(int i = 1; i<=n; i++) {
        if (!visited[i] && board[position][i]) {
            dfs(i);
        }
    }
}
 
int main() {
 
    std::ios::sync_with_stdio(false); cin.tie(0);
 
    cin >> n >> m;
 
    for(int i=0; i<m; i++) {
        int x, y; cin >> x >> y;
        board[x][y] = board[y][x] = 1;
    }
 
    int sol =0 ;
    for(int i=1; i<=n; i++) {
        if (visited[i] == 0) {
            sol++;
            dfs(i);
        }
    }
 
    cout << sol << "\n";
 
    return 0;
}