[백준] 11724 연결 요소의 개수 c++

 

문제 링크 https://www.acmicpc.net/problem/11724

평범한 dfs 문제였다.

1~6번까지의 노드가 있고, 1-2-3  4-5-6 이렇게 두개의 연결그래프가 있다고 예를 들어보면,

1부터 6까지 모든 노드를 탐색하면서 탐색을 할 때마다 카운트를 세주면 된다.

그렇게 되면 1번, 4번노드에서 각각 dfs를 하여 총 두번 탐색이 이루어진다. 

 

Code

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<cstring>
const int MAX = 1001;
using namespace std;
int n, m;
vector<vector<int>> v;
bool visited[MAX];
int cnt;
 
void dfs(int node) {
    for (int i = 0; i < v[node].size(); i++) {
        int next = v[node][i];
        if (visited[next])
            continue;
 
        visited[next] = true;
        dfs(next);
    }
}
int main()
{
    cin >> n >> m;
    v.resize(n+1);
    for (int i = 1; i <= m; i++) {
        int first, second;
        cin >> first >> second;
        v[first].push_back(second);
        v[second].push_back(first);
    }
    for (int i = 1; i < v.size(); i++) {
        if (!visited[i]) {
            visited[i] = true;
            dfs(i); 
            cnt++; //탐색할 때마다 카운트 증가
        }
    }
    cout << cnt;
}