[Baekjoon] 11724번: 연결 요소의 개수

🥅 문제

https://www.acmicpc.net/problem/11724

 

🔍 설계

서로소 집합을 사용하여 연결된 것들끼리 그룹을 형성하게 한다.

 

그룹의 수는 맨 꼭대기에 있는 조상의 수이다.

 

문제 입력 순서에 따라 parent[x]가 맨 꼭대기 조상이 아닐 수 있으므로, find_parent(x)로 맨 꼭대기 조상을 집합에 삽입한다.

 

---

BFS로 방문처리를 하여 영역의 개수를 구하여 해결할 수도 있다.

 

👊 풀이1

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

int n, m, u, v;
vector<int> parent(1001);
set<int> result;

int find_parent(int x) {
	if (parent[x] != x) {
		return find_parent(parent[x]);
	}
	return parent[x];
}

void union_parent(int a, int b) {
	a = find_parent(a);
	b = find_parent(b);
	if (a < b) {
		parent[b] = a;
	}
	else {
		parent[a] = b;
	}
}

int main(void)
{	
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> m;

	for (int i = 1; i <= n; i++) {
		parent[i] = i;
	}

	for (int i = 0; i < m; i++) {
		cin >> u >> v;
		union_parent(u, v);
	}
	
	for (int i = 1; i <= n; i++) {
		result.insert(find_parent(i));
	}
	cout << result.size() << "\n";

	return 0;
}

 

👊 풀이2

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

int n, m, u, v, result = 0;
vector<int> visited(1001);
vector<vector<int>> adj_list(1001);

void bfs(int start) {
	visited[start] = true;
	queue<int> q;
	q.push(start);
	while (!q.empty()) {
		int cur = q.front();
		q.pop();
		int size = adj_list[cur].size();
		for (int i = 0; i < size; i++) {
			int next = adj_list[cur][i];
			if (!visited[next]) {
				visited[next] = true;
				q.push(next);
			}
		}
	}
}

int main(void)
{	
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> m;

	for (int i = 0; i < m; i++) {
		cin >> u >> v;
		adj_list[u].push_back(v);
		adj_list[v].push_back(u);
	}

	for (int i = 1; i <= n; i++) {
		if (!visited[i]) {
			result += 1;
			bfs(i);
		}
	}

	cout << result << "\n";

	return 0;
}