문제 링크

코드 설명

이 문제는 Unionfind로 푸는것이 먼저 떠올랐지만, 우선 BFS로 한번 풀고 Unionfind로도 다시 풀어보았다.

BFS로 풀때는 main에서 visit배열을 통해 지나지않은 정점(즉 아직 연결 되지 않은)을 찾아서 카운트를 늘려주고 접근해야 한다.

또한, Unionfind를 연습해보기 좋은 문제였다.

소스 코드

😊 BFS 버전

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>

using namespace std;
int n, m;
vector<int> graph[1001];
bool visited[1001];
void bfs(int start) {
	queue<int> q;
	q.push(start);
	visited[start] = true;

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

		for(int i=0;i<graph[a].size();i++){
			int next = graph[a][i];
			if (!visited[next]) {
				visited[next] = true;
				q.push(next);
			}

		}
	}

}
int main() {
	cin >> n >> m;

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

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



	return 0;
}

😊 Union-Find 사용

#include <iostream>
#include <vector>
#include <queue>

using namespace std;
int vect[1001];

int getBoss(int target) {
	if (vect[target] == 0) {
		return target; //자기 자신이 boss
	}

	int ret = getBoss(vect[target]);

	return ret; //마지막 boss return

}
void makeGroup(int t1, int t2)
{
	int a = getBoss(t1);
	int b = getBoss(t2);
	if (a == b) return;
	vect[b] = a;

}
int main() {
	int n, m;
	int a, b;

	cin >> n >> m;

	for (int i = 0; i < m; i++) {
		cin >> a >> b;
		makeGroup(a, b);
	}
		int cnt = 0;

	for (int j = 1; j <= n; j++) {
		if (vect[j] == 0) cnt++;

	}
	cout << cnt;




	return 0;
}