BOJ 11724 연결 요소의 개수

문제출처 : https://www.acmicpc.net/problem/11724

1. 문제요약

- 컴포넌트의 갯수는?

2. 접근방법

- bfs, dfs

3. 시간복잡도

- O(VE)

4. 회고

- 다른사람보다 시간이 걸린이유는 입력속도의 차이라고 생각함

소스코드 : bfs

#include<iostream>
#include<queue>
#include<vector>
using namespace std;

int n, m, ans = 0, check[1001];

int main(void){
	cin >> n >> m;
	vector<vector<int> > g(n + 1);
	int a, b;
	for (int i = 0; i < m; i++){
		cin >> a >> b;
		g[a].push_back(b);
		g[b].push_back(a);
	}

	queue<int> q;
	for (int i = 1; i < n + 1; i++){
		if (!check[i]){
			ans++;
			q.push(i);
			check[i] = true;

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

				for (int j = 0; j < g[now].size(); j++){
					if (!check[g[now][j]]){
						q.push(g[now][j]);
						check[g[now][j]] = true;
					}
				}
			}
		}
	}
	cout << ans << "\n";
	return 0;
}

소스코드 : dfs

#include<iostream>
#include<vector>
using namespace std;

int n, m, ans, check[1001];
vector<vector<int> > g;

void dfs(int now){
	check[now] = true;

	for (int i = 0; i < g[now].size(); i++){
		if (!check[g[now][i]])
			dfs(g[now][i]);
	}
}

int main(void){
	cin >> n >> m;
	g.resize(n + 1);
	int a, b;
	for (int i = 0; i < m; i++){
		cin >> a >> b;
		g[a].push_back(b);
		g[b].push_back(a);
	}

	for (int i = 1; i < n + 1; i++){
		if (!check[i]){
			ans++;
			dfs(i);
		}
	}
	cout << ans << "\n";
	return 0;
}

[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]