백준 #11724

★☆☆☆☆☆☆☆☆☆

---

문제 접근 방법

연결 요소의 개수는 bfs와 dfs로 둘 다 해결 가능한데 bfs가 조금 미숙하다고 생각해 bfs로 문제를 풀었다.  bfs나 dfs를 모든 정점에서 시작을 하고  visit [] 배열에 이미 방문한 정점은 true로 처리해준다. 이후에 visit이 false인 정점에서만 시작하고 bfs와 dfs는 연결된 모든 정점을 정말 탐색하기 때문에,  bfs 나 dfs 함수가 실행되는 횟수는 연결 요소의 개수를 뜻한다. 

---

#include<iostream>
using namespace std;
bool visited[1001];
bool arr[1001][1001];
int N, M;
int cnt;
void dfs(int vertex) {
	visited[vertex] = true;
	for (int i = 1; i <= N; i++) {
		if (arr[i][vertex] && visited[i] == 0) {
			dfs(i);
		}
	}
}
void is_connected() {
	for (int i = 1; i <= N; i++) {
		if (!visited[i]) {
			dfs(i);
			cnt++;
		}
	}
	cout << cnt;
}
int main() {
	cin >> N >> M;
	int num1, num2;
	while (M--) {
		cin >> num1 >> num2;
		arr[num1][num2] = true;
		arr[num2][num1] = true;
	}
	is_connected();
}