[백준 11724] 연결요소의 개수

문제 요약

그래프가 주어진다. connected component의 수를 구하라.

풀이

bfs(dfs도 됩니다만)를 활용해 connected component의 수를 구했다.

seed 찾는 데에 쓴 가성비

seed 찾을 때... 그냥 무지성으로 찾는다면 매번 1번부터 1000번까지 쭉 찾았겠지만 seed 찾는 과정을 노드 개수만큼만 하기 위해 이전 시드를 받아와서 그 다음부터 찾았다.

int get_seed(int last_seed, int n) {
	for (int i = last_seed + 1; i <= n; i++) {
		if (!visited[i]) return i;
	}
	return -1;
}

소스코드

#include<iostream>
#include<vector>
#include<memory.h>
#include<queue>
using namespace std;
//그래프가 주어질 때 connected component의 개수를 구하라
bool visited[1001];
void bfs(int seed,vector<int> g[]) {
	queue<int> q;
	q.push(seed);
	visited[seed] = true;
	while (!q.empty()) {
		int me = q.front();
		q.pop();
		for (int i = 0; i < g[me].size(); i++) {
			if (!visited[g[me][i]]) {
				q.push(g[me][i]);
				visited[g[me][i]] = true;
			}
		}
	}
}
int get_seed(int last_seed, int n) {
	for (int i = last_seed + 1; i <= n; i++) {
		if (!visited[i]) return i;
	}
	return -1;
}

int main() {

	int n, m;
	cin >> n >> m;
	vector<int> g[1001];
	int a, b;
	for (int i = 0; i < m; i++) {
		cin >> a >> b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	//bfs
	bool visited[1001];
	memset(visited, false, sizeof visited);
	queue<int> q;
	q.push(1);
	visited[1] = true;
	while (!q.empty()) {
		int me = q.front();
		q.pop();
		for (int i = 0; i < g[me].size(); i++) {
			if (!visited[g[me][i]]) {
				q.push(g[me][i]);
				visited[g[me][i]] = true;
			}
		}
	}
	memset(visited, false, sizeof visited);
	int seed = 0;
	int comp = 0;
	while ((seed = get_seed(seed, n)) != -1) {
		bfs(seed, g);
		comp++;
	}

	cout << comp;
}