[알고리즘 문제풀이] 유니온파인드#1

#include<iostream>
#include<vector>
#include<algorithm>
#include<list>
#include<string>
#include<map>

using namespace std;

char parent[256] = {};

int group = 4;

char getParent(char x) {
	if (parent[x] == 0) 
		return x;
	
	int ret = getParent(parent[x]);
	parent[x] = ret;

	return ret;
}

void merge(char ma, char mb) {
	int a = getParent(ma);
	int b = getParent(mb);
	if (a != b) {
		parent[b] = a; // b의 부모를 a로 설정
		group--;
	}
}

void insert(char ch1, char ch2) {
	int a = getParent(ch1);
	int b = getParent(ch2);

	if (a != b) {
		parent[b] = a; // b의 부모를 a로 설정
	}
}

int main() {

	insert('A', 'B');
	insert('B', 'C'); // 그룹 1
	insert('D', 'E'); // 그룹 2
	insert('E', 'F');
	insert('G', 'H'); // 그룹 3
	insert('I', 'J'); // 그룹 4

	int n;
	cout << "그룹핑을 몇번 하시겠습니까?";
	cin >> n;
	for (int i = 0; i < n; i++) {
		char a, b;
		cin >> a >> b;
		merge(a, b);
	}
	cout << "최종 그룹의 수 " << group << endl;
	return 0;
}