BFS/ DFS - 백준 11724 연결 요소의 개수 C++

1. 문제

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

2.  입력

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2)

둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v)

같은 간선은 한 번만 주어진다.

3.  출력 

첫째 줄에 연결 요소의 개수를 출력한다.

 

4.  예제

5.  답안

#include <iostream>
#include <vector>
using namespace std;
 
int n,m;
vector <int> graph[1001];
int count = 0;
bool visited[1001] = {false, }; 
 
void dfs(int start){
    if(visited[start]){
        return ;
    }else{
       visited[start] = true;
       
       for(int i = 0 ; i<graph[start].size() ; i++){
           int node = graph[start][i];
           if(!visited[node]){
               dfs(node);
           }
       } 
    }
}
 
int main(){
    cin >> n >> m ;
    
    for (int i = 0 ; i < m ; i++){
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    
    for(int i = 1 ; i <= n ; i++){
        if(!visited[i]){
            dfs(i);
            count++;
        }
    }
    cout <<count <<endl;
    
    return 0;
    
}