[C++]BOJ 11724 - 연결 요소의 개수

단순한 탐색 문제다.
모든 노드를 간선을 따라 탐색하며 방문처리를 한 후, 방문을 안한 노드가 있다면 모든 노드를 방문할 때 까지 탐색하고 총 탐색 횟수를 출력하면 된다.
dfs와 bfs모두 쓸 수 있다.

bfs로 이 문제 풀다가 시간초과가 났는데 얼타다가 생각해보니 방문처리를 큐에서 뺀 후가 아니라 넣은 후에 해줘야 했다는걸 간과했다. 기억할것

bfs

#include <iostream>
#include <queue>
using namespace std;
int n, m, arr[1002][1002], vs[1002], u, v, tmp, ans;
queue<int> q;
void bfs(int s) {
	q.push(s);
	while(!q.empty()) {
		s = q.front(); q.pop();
		for(int i = 1; i <= n; i++) {
			if(!arr[s][i] || vs[i]) continue;
			q.push(i);
			vs[i] = 1;
		}
	}
}
int main() {
	cin >> n >> m;
	while(m--) {
		cin >> u >> v;
		arr[u][v] = arr[v][u] = 1;
	}
	for(int i = 1; i <= n; i++)
		if(!vs[i]) {
			bfs(i);
			ans++;
		}
	cout << ans;
}

dfs

#include <iostream>
using namespace std;
int n, m, arr[1002][1002], vs[1002], u, v, tmp, ans;
void dfs(int s) {
	vs[s] = 1;
	for(int i = 1; i <= n; i++) {
		if(vs[i]) continue;
		if(arr[s][i]) dfs(i);
	}
}
int main() {
	cin >> n >> m;
	while(m--) {
		cin >> u >> v;
		arr[u][v] = arr[v][u] = 1;
	}
	for(int i = 1; i <= n; i++)
		if(!vs[i]) {
			dfs(i);
			ans++;
		}
	cout << ans;
}