SWEA - 창용 마을의 개수 (C++)

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWngfZVa9XwDFAQU

SW Expert Academy

 

기본적인 유니온 파인드 기본 문제이다.

 

유니온 파인드는 이름부터 유니온과 파인드 함수로 나뉜다.

 

유니온은 함께 묶기, 파인드는 부모를 찾는 것이다.

 

그리고 기본적으로 유니온 파인드는 사이클을 찾기 위해서 사용되기도 하는데, 무방향 그래프는 DFS와 유니온 파인드로. 방향 그래프는 DFS로 알 수 있다.

 

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

int people[101];

int Find(int x) {
	if (people[x] == x) return x;
	else people[x] = Find(people[x]);
}
void Union(int x, int y) {
	int px = Find(x);
	int py = Find(y);

	if (px < py) people[py] = px;
	else people[px] = py;
}

int main() {
	int T; cin >> T;

	for (int t = 1; t <= T; t++) {
		int N, M;
		cin >> N >> M;

		for (int i = 1; i <= N; i++) {
			people[i] = i;
		}

		for (int i = 0; i < M; i++) {
			int a, b; cin >> a >> b;
			Union(a, b);
		}
		set<int> s;
		for (int i = 1; i <= N; i++) {
			//cout << people[i] << endl;
			s.insert(Find(i));
		}

		cout << '#' << t << ' ' << s.size() << '\n';
	}
}