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

문제

 

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

---

풀이

BFS를 이용해 모든 노드를 탐색하고 연결 요소의 개수를 구하는 방법으로 풀이했다.

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

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

using namespace std;

int N, M;
vector<int> vec[1001];

bool visited[1001] = { false, };

void BFS(int startPos) {
	queue <int>q;

	q.push(startPos);
	visited[startPos] = true;

	while (!q.empty()) {
		int target = q.front();
		q.pop();


		for (int i = 0; i < vec[target].size(); i++) {
			if (!visited[vec[target][i]]) {
				visited[vec[target][i]] = true;
				q.push(vec[target][i]);
			}
		}
	}
}

int main() {
	cin >> N >> M;

	int s1, s2;
	for (int i = 0; i < M; i++) {
		cin >> s1 >> s2;
		vec[s1].push_back( s2 );
		vec[s2].push_back( s1 );
	}

	int count = 0;
	for (int i = 1; i <= N; i++) {
		if (!visited[i]) {
			BFS(i);
			count++;
		}
	}

	cout << count;
	return 0;
}