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

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

11724번: 연결 요소의 개수

해당 문제는 N개의 정점과 M개의 간선들이 주어질 때 하나로 연결 된 요소들의 총 개수를 구하는 문제이다.

풀이 :

for 문을 사용하여 N개의 정점을 BFS를 사용하여 탐색하며 탐색한 정점은 check 해주며 Check 되지 않은 정점이 있을 경우 해당 정점에서 다시 BFS를 사용하여 정점을 탐색하는 과정을 반복하면서 check되지 않은 정점들의 개수를 모두 구하면 몇개의 요소가 있는지 알 수 있다.

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int n, m;
int used[1001];
vector<int> map[1001];


void bfs(int v){
	queue<int> qu;
	qu.push(v);
	used[v] = 1;

	while (!qu.empty()){
		int now = qu.front();
		for (int i = 0; i < map[now].size(); ++i){
			if (used[map[now][i]] == 1) continue;
			used[map[now][i]] = 1;
			qu.push(map[now][i]);
		}
		qu.pop();
	}

}

int main(){
	freopen_s(new FILE*, "tes.text", "r", stdin);
	cin >> n >> m;
	int cnt = 0;
	for (int i = 0; i < m; ++i){
		int a, b;
		cin >> a >> b;
		map[a].push_back(b);
		map[b].push_back(a);
	}

	for (int i = 1; i <= n; ++i){
    	// 탐색 된 정점일 경우 continue
		if (used[i] == 1) continue;
		++cnt;
		bfs(i);
	}
	cout << cnt;


}