[백준 11724, c++] 연결 요소의 개수(bfs, dfs)

문제 번호

• 11724(https://www.acmicpc.net/problem/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

6 5 1 2 2 5 5 1 3 4 4 6

예제 출력1

2

 

예제 입력2

6 8 1 2 2 5 5 1 3 4 4 6 5 4 2 4 2 3

예제 출력2

1

 

문제 풀이

연결 요소(Connected Component)의 수를 구하는게 주 목적이므로, 

 

중요 point

별건없지만 이 부분의 코드가 핵심이다.

 

BFS 또는 DFS를 통해 완전탐색을 진행하되 각각의 정점(n)마다 방문여부를 체크하고, 방문하지 않았다면 카운터를 세는것이다. 

 

cnt가 1이라면 모든 정점들이 연결되있다고 볼 수있고,

그 이상이라면 정점들의 무리가 다르다고 볼 수 있다.

 

 

1.  정점의 개수, 간선의 개수를 입력받는다.

2. 간선이 연결하는 두 정점의 번호를 벡터를 이용하여 입력받아 연결한다.

3. DFS와 BFS 탐색을 통해 완전탐색을 진행하고, 각각의 정점탐색 시작마다 방문여부를 체크하고, 조건 해당시카운터를 센다.

4. 카운트된 연결 요소의 개수를 출력한다.

 

 

예제 1

 

예제2

소스 코드

#include <iostream>
#include <queue>
#include <vector>
#include <stdio.h>
#include <cstring> // memset
 
#define MAX_SIZE 1000+1
 
using namespace std;
 
void dfs(int start);
void bfs(int start);
 
vector<int> connected[MAX_SIZE];
bool visited[MAX_SIZE];
 
void dfs(int start) {
    visited[start] = true;
    for (int i = 0; i < connected[start].size(); i++) {
        int next = connected[start][i];
        if (!visited[next]) {
            dfs(next);
        }
    }
}
 
void bfs(int start) {
    queue<int> q;
 
    visited[start] = true;
    q.push(start);
    while (!q.empty()) {
        int current = q.front();
        q.pop();
 
        int csize = connected[current].size();
        for (int i = 0; i < csize; i++) {
            int next = connected[current][i];
            if (!visited[next]) {
                visited[next] = true;
                q.push(next);
            }
        }
    }
}
 
int main() {
    int n, m; // 정점의 개수, 간선의 개수
    scanf("%d %d", &n, &m);
    for (int i = 0; i < m; i++) { // 간선의 연결
        int u, v;
        scanf("%d %d", &u, &v);
        connected[u].push_back(v);
        connected[v].push_back(u);
    }
 
    int cnt = 0;
    memset(visited, false, sizeof(visited));
    for (int i = 1; i <= n; i++) {
        if (!visited[i]) {
            cnt++;
            bfs(i);
            //dfs(i);
        }
    }
    printf("%d\n", cnt);
    return 0;
}