[백준] 11724번 : 연결 요소의 개수 (C++)

11724번 : 연결 요소의 개수

---

문제 )

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

 

입력 :

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.

 

 

 

출력 :

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

 

 

 

 

 

풀이)

예제 1번을 그림을 그려보면 다음과 같이 그려진다. 

 

이렇게 해서 연결 요소의 개수가 2개라는 의미이므로,

 

다음과 같이 코드를 짜면 된다.

 

#include <iostream>
#include <vector>
 
using namespace std;
 
vector<vector<int>> vec;
vector<int> visited;
 
 
// 일반적인 dfs 사용
void dfs(int x)
{
    if (visited[x] == 1) return;
    visited[x] = 1;
 
    for (int i = 0; i < vec[x].size(); i++)
    {
        dfs(vec[x][i]);
    }
}
 
int main()
{
    int n, m;
    cin >> n >> m;
 
    // vector 사용을 위해 resize
    vec.resize(n + 1);
    visited.resize(n + 1);
 
    // 방향없는 양방향 간선이므로
    int a, b;
    for (int i = 0; i < m; i++)
    {
        cin >> a >> b;
        vec[a].push_back(b);
        vec[b].push_back(a);
    }
 
 
    // 숫자를 세기 위한 count
    int count = 0;
    // 1번 노드부터 n번 노드까지 다 dfs를 돌리는데,
    // 이미 방문한 노드라면 넘어간다.
    for (int i = 1; i < n + 1; i++)
    {
        if (visited[i] == 1) continue;
        dfs(i);
        count++;
    }
 
    // 연결 요소의 개수를 출력
    cout << count;
 
    return 0;
}
 

 

---

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

11724번: 연결 요소의 개수