[BFS, 합집합] 백준 11724번 연결 요소의 개수 (2가지 방법)

BFS 기준으로는 난이도 하, 합집합 기준으로는 난이도 중하를 주고싶다.

1. BFS 알고리즘

꼬지 않은 평범한 BFS 문제이다. 평균 BFS 알고리즘 문제 정답율보다 높은 편인 46%의 정답율을 가지고 있는데

연결 요소가 몇 개인지, 다른 말로 몇 개의 연결그룹으로 되어있는지 계산하는 문제이다.

 FOR문으로 모든 정점을 탐색하여 방문하지 않은 노드에 대해서만 BFS를 수행하고, while문이 끝날 때 그룹 수를 1씩 더해주면 해결 된다. 

 

 

#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
#include <queue>
#include <stack>
#include <string>
using namespace std;
vector<int> a[1001];
bool visited[1001];
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n, m;
	int ans = 0;
	cin >> n >> m;
	queue<int> q;
	for (int i = 0; i < m; i++) {
		int x, y;
		cin >> x >> y;
		a[x].push_back(y);
		a[y].push_back(x);
	}
	for (int i = 1; i <= n; i++) {
		if (!visited[i]) {
			visited[i] = true;
			q.push(i);
			while (!q.empty()) {
				int f = q.front();
				q.pop();
				for (int j = 0; j < a[f].size(); j++) {
					int d = a[f][j];
					if (!visited[d]) {
						visited[d] = true;
						q.push(d);
					}
				}
			}
			ans++;
		}
	}
	cout << ans;
}

 

2. 합집합 알고리즘

아래 사진은 예제 1번을 그린 것이다.

합집합 알고리즘은 BFS처럼 연결 요소끼리 집합을 판단할 수 있게 한다.

부모는 두 노드를 비교했을 때 작은 숫자의 노드로 했다.

2,5의 부모 -> 1

4,6의 부모 -> 3

함수설명

get_parent : parent 배열을 참조하여 재귀적으로 최종 부모를 찾는다.

_union : 두 노드의 최종 부모를 비교하여 작은 숫자의 노드를 부모로 정한다.

 

 

#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
#include <queue>
#include <stack>
#include <string>
using namespace std;
vector<int> a[1001];
int parent[1001];
int countparent[1001];

int get_parent(int parent[], int x) {
	if (parent[x] == x) return x;
	else return parent[x] = get_parent(parent, parent[x]);
}
void _union(int parent[], int x, int y) {
	x = get_parent(parent, x);
	y = get_parent(parent, y);
	if (x < y)parent[y] = x;
	else parent[x] = y;
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n, m;
	int ans = 0;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) parent[i] = i;
	for (int i = 0; i < m; i++) {
		int x, y;
		cin >> x >> y;
		_union(parent, x, y);
	}
	for (int i = 1; i <= n; i++) {
		int p = get_parent(parent, i);
		countparent[p]++;
	}
	for (int i = 1; i <= n; i++) {
		if (countparent[i] > 0) ans++;
	}
	cout << ans;
}