SWEA 7465번 창용 마을 무리의 개수 C++ 유니온 파인드 Union-Find

리뷰

 

SW Expert Academy

 

전형적인 유니온 파인드 문제, 기본적인 코드만 구현하면 해결할 수 있는 문제이다.

 

문제 풀이

1. 테스트 케이스 마다 init 함수를 실행하여 ans를 0으로, 1 ~ n의 노드를 자기 자신을 value로 갖도록 nodes배열을 초기화 한다.
2. query함수를 통해 m개의 간선을 입력 받고 두 노드를 Union 처리를 해준다.
3. solution 함수를 통해 1 ~ n개의 노드 각각을 Find하여 부모를 최신화 하고 자기 자신을 value로 가진 노드를 발견했을 경우 ans를 증가 시켜준다.
4. 각 테스트 케이스 마다 ans 값을 출력해 주면 된다.

 

참고 사항

Union 처리 후 자기 자신을 value로 갖고 있는 노드가 부분 집합의 대표 노드가 된다.

대표 노드의 개수가 결국 부분 집합의 개수를 나타내게 된다.

 

정답 코드

#include<iostream>

using namespace std;

int nodes[101];
int tc, n, m, ans;

void init() {
	ans = 0;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) nodes[i] = i;
}

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

void Union(int a, int b) {
	int A = Find(a);
	int B = Find(b);
	if (A == B) return;
	nodes[B] = A;
}

void query() {
	while (m--) {
		int a, b; cin >> a >> b;
		Union(a, b);
	}
}

void solution() {
	for (int i = 1; i <= n; i++) {
		Find(i);
		if (nodes[i] == i) ans++;
	}
}

int main() {
	cin >> tc;
	for (int c = 1; c <= tc; c++) {
		init();
		query();
		solution();
		cout << "#" << c << " " << ans << "\n";
	}
}