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

1. 문제설명

무방향 그래프가 주어지고 노드와 간선간의 정보가 주어졌을 때

연결 요소 (Connected Component)의 개수를 구하는 문제입니다.

연결 요소의 개수는

서로 연결되어 있는 집합이 몇개인 지 구해야 합니다.

위 그림과 같은 경우 Connected Component는 2개 입니다.

2.접근방법[알고리즘]

먼저 떠오르는 해결 방법은

모든 노드 간선 정보를 바탕으로 그래프를 만들고

BFS나 DFS로 탐색하면서 방문한 노드를 체크하면서

방문하지 않은 새로운 노드를 발견할 때마다 정답으로 출력할 변수에 +1을 해주면 구할 수 있습니다.

한번 더 나아가면 Union & Find 알고리즘을 이용해

서로 연결되어있는 노드는 같은 집합으로 분류해주고

부모노드의 개수를 세면 집합의 개수를 알 수 있습니다.

Union & Find 알고리즘을 이용하면 BFS나 DFS보다 시간을 절약해서 풀 수 있습니다.

3.문제풀이코드 C++

1. Union & Find C++

#include <bits/stdc++.h>
using namespace std;

int n, m , unf[1001], ans;

int Find(int a) {
	if (a == unf[a]) {
		return a;
	}
	else {
		return unf[a] = Find(unf[a]);
	}
}

void Union(int a, int b) {
	a = Find(a);
	b = Find(b);

	if (a > b) {
		swap(a, b);
	}

	if (a != b) {
		unf[a] = b;
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;

	for (int i = 0; i <= 1000; i++) {
		unf[i] = i;
	}

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

	// 부모 노드의 개수 == 같은 집합의 개수
	for (int i = 1; i <= n; i++) {
		if (unf[i] == i) ans++;
	}
	cout << ans << '\n';



	return 0;

}

2. BFS

#include <bits/stdc++.h>
using namespace std;

int n, m;

bool ch[1001];
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;

	vector<int> map[1001];

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

		map[a].push_back(b);
		map[b].push_back(a);
	}
	int ans = 0;
	queue<int> Q;
	for (int i = 1; i <= n; i++) {
		if (!ch[i]) {
			ans++;
			ch[i] = 1;
			Q.push(i);
			while (!Q.empty()) {
				int x = Q.front();
				Q.pop();
				for (int j = 0; j < map[x].size(); j++) {
					if (ch[map[x][j]] == 0) {
						ch[map[x][j]] = 1;
						Q.push(map[x][j]);
					}
				}
			}
		}
	}

	cout << ans << '\n';

	return 0;

}

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

1. 문제 설명

첫째 줄에 별의 개수 n이 주어진다. (1 ≤ n ≤ 100)

둘째 줄부터 n개의 줄에 걸쳐 각 별의 x, y좌표가 실수 형태로 주어지며,
최대 소수점 둘째자리까지 주어진다. 좌표는 1000을 넘지 않는 양의 실수이다.

별이 n개 주어지고 별들의 각각 좌표가 주어진다.

모든 별을 이용해서 최소 거리, 비용으로 별자리를 만들어야한다.

2. 접근 방법[알고리즘]

최소 비용으로 모든 별을 이어야 하므로 최소스패닝트리, 최소 신장 트리(MST)를 만들어야한다.

크루스칼 알고리즘이나 프림 알고리즘을 사용해서 만들면 된다.

나는 크루스칼 알고리즘을 이용했다.

3. 문제풀이코드 C++

#include <bits/stdc++.h>
using namespace std;

int unf[10001];

struct Edge{
	int v1;
	int v2;
	double val;
	Edge(int a, int b, double c){
		v1=a;
		v2=b;
		val=c;
	}
	bool operator<(const Edge &b) const{
		return val>b.val;
	}
};

int Find(int v){
	if(v==unf[v]) return v;
	else return unf[v]=Find(unf[v]);
}

void Union(int a, int b){
	a=Find(a);
	b=Find(b);
	if(a!=b) unf[a] = b;
}

double dist(pair<double, double> &a , pair<double, double> &b){
	return sqrt(pow(a.first-b.first,2) + pow(a.second - b.second,2));
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	priority_queue<Edge> Q;
	double res=0;
	int n;
	vector<pair<double, double> > star;
	
	cin >> n;
	for(int i=0; i<n; i++){
		double x,y;
		cin >> x >> y;
		star.push_back(make_pair(x,y));
	}
	
	for(int i=0; i<n; i++){
		for(int j=i+1; j<n; j++){
			Q.push(Edge(i,j, dist(star[i],star[j])));
		}
	}
	
	for(int i=0; i<n; i++){
		unf[i] = i;
	}
	
	
	while(!Q.empty()){
		int node_a = Q.top().v1;
		int node_b = Q.top().v2;
		double d = Q.top().val;
		Q.pop();
		
		if(Find(node_a)!=Find(node_b)){
			Union(node_a, node_b);
			res += d;
		}		
	}
	cout << fixed;
	cout.precision(3);
	cout << res ;
	
	
}

문제에서 출력을 절대/상대 오차 10-2까지 허용한다고 해서

아예 소수 세번째 자리까지 출력했다.

출력과정에서 반올림이 될 수도 있다고 생각해서 널널하게 세번째까지 출력했다.

input을 star에 입력해주었다.

그리고 모든 star 요소에 대해서 각 거리를 구해 우선순위 큐(최소힙)에 넣고

두 별 사이의 거리가 최소인 Edge를 최소힙에서 꺼내서 Union&Find 알고리즘을 이용하여

이미 두 별이 연결되어 있으면 넘어가고, 연결되어 있지 않으면 연결해주고

그 두 별 사이의 거리를 res 변수에 더해주었다.

최소스패닝트리를 구하는 걸 연습하기 좋은 문제다.

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

#include <iostream>
#include <algorithm>
#include <cstring>
#include <map>
#include <set>

using namespace std;

int unf[200002], sizes[2000002];

int Find(int x){
	if (x==unf[x]) return x;
	else return unf[x] = Find(unf[x]);
}

void Union(int a, int b){
	a = Find(a);
	b = Find(b);
	
	if(a!=b){
		if(sizes[a]<sizes[b]) swap(a,b);
		sizes[a] += sizes[b];
		unf[b] = a;
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	int t;
	cin >> t;
	for(int T=0; T<t; T++){
		int a;
		map<string, int> m;
		int node = 1;
		string s1, s2;
		cin >> a;
		
		for(int i=0; i<200002;i++){
			unf[i] = i;
			sizes[i] = 1;
		}
		
		
		for(int i=0; i<a; i++){
			cin >> s1 >> s2;
			if(m.count(s1)==0) m[s1]=node++;
			if(m.count(s2)==0) m[s2]=node++;
			
			Union(m[s1],m[s2]);
			
			
			cout << max(sizes[Find(m[s1])], sizes[Find(m[s2])]) << '\n';
			
		}
	}
	
	
}