[Baekjoon] 연결 요소의 개수

👀 문제 설명

문제

방향 없는 그래프가 주어졌을 때, 연결 요소 (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

✍🏻풀이

연결 요소란, 

그래프가 위와 같을 때, 네 개의 연결 요소가 있다고 한다.

연결 요소의 개수를 구할 땐, 보통 DFS나 BFS로 푼다.

 

정점을 방문했는지 저정하는 배열 visited를 선언하고, 이를 사용해 연결 요소의 개수를 구해준다.

getConnected(int start) 함수는 start가 어떤 연결 요소에 속할 때, 그 연결 요소에 속하는 다른 정점들을 다 방문하고, visited 값을 1로 바꿔준다. (즉, getConnected 함수가 호출되고, 이 함수가 끝나면 하나의 연결 요소의 정점을 모두 방문했다는 뜻이다)

이제 1부터 N까지 접근해 연결 요소의 개수를 구해주면 된다.

 

코드

#include <stdio.h>
#include <iostream>
#include <vector>
#include <queue>

#define MAX 1001

using namespace std;

int N, M;
int visited[MAX];
vector<pair<int, int>> vec;
int answer;

// 한 연결 요소에 속하는 원소들을 다 방문한다
void getConnected(int start) {
    queue<int> Q;
    
    Q.push(start);
    visited[start] = 1;
        
    while (!Q.empty()) {
        int cur = Q.front(); Q.pop();
        
        for (int i = 0; i < vec.size(); i++) {
            int u = vec.at(i).first;
            int v = vec.at(i).second;
            
            if (u == cur && visited[v] == 0) {
                Q.push(v);
                visited[v] = 1;
            }
            else if (v == cur && visited[u] == 0) {
                Q.push(u);
                visited[u] = 1;
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N >> M;
    
    for (int i = 0; i < M; i++) {
        int u, v;
        cin >> u >> v;
        
        vec.push_back({ u, v });
    }
    
    for (int i = 1; i <= N; i++) {
        if (visited[i] == 0) { // 한 연결요소가 끝나면 answer에 1을 더한다
            getConnected(i);
            answer++;
        }
    }
    
    cout << answer << "\n";
    
    return 0;
}