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

문제

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

입력

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

출력

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

---

그래프의 연결 요소의 수를 구하는 문제이다. 

연결 요소가 뭔지 몰랐지만 예제를 보니 대충 그래프가 몇개로 나뉘는가에대한 질문이란걸 깨달았고, bfs로 문제를 풀었다.

bfs는 단순히 연결된 점들을 방문하는것이고, 방문되지 않은 점마다 bfs를 실행한다.

그 실행 회수가 바로 연결 요소의 개수가 된다.

 

 

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/BaekJoon/2020/%EC%97%B0%EA%B2%B0%20%EC%9A%94%EC%86%8C%EC%9D%98%20%EA%B0%9C%EC%88%98%20(11724%EB%B2%88).cpp

chosh95/STUDY

C++ 코드

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
vector<int> map[1001];
int N, M;
int visit[1001];

void bfs(int start)
{
	queue<int> q;
	q.push(start);
	visit[start] = 1;
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		for (int i = 0; i < map[x].size(); i++) {
			int nx = map[x][i];
			if (visit[nx] == 1) continue;
			q.push(nx);
			visit[nx] = 1;
		}
	}
}

int main()
{
	cin >> N >> M;
	for (int a, b, i = 0; i < M; i++) {
		cin >> a >> b;
		map[a].push_back(b);
		map[b].push_back(a);
	}
	int res = 0;
	for (int i = 1; i <= N; i++) {
		if (!visit[i]) {
			bfs(i);
			res++;
		}
	}
	cout << res;
}