lev33 : union find

#include <iostream>
using namespace std;

int myBoss[10];
int find(int n) {
	if (myBoss[n] == 0) {
		return n;
	}
	int ret = find(myBoss[n]);
	return ret;
}
void setunion(int t1,int t2) {
	//t2가 t1에 들어가려고 했는데,,
	//이미 같은 보스인경우
	int a = find(t1);
	int b = find(t2);
	if (a == b)return;
	myBoss[b] = a;
}
int main() {
	setunion(1, 2);

	return 0;
}

union find 연습

#include <iostream>
using namespace std;
int N, M;
int myBoss[10];
int find(int n) {
	if (myBoss[n] == 0) {
		return n;
	}
	return myBoss[n] = find(myBoss[n]);
}
void setBoss(int t1, int t2) {
	int a = find(t1);
	int b = find(t2);
	if (a == b)return;
	myBoss[b] = a;
}
int main() {
	freopen_s(new FILE*, "input.txt", "r", stdin);

	cin >> N;
	for (int i = 0; i < N; i++) {
		int a, b;
		cin >> a >> b;
		setBoss(a, b);
	}
	cin >> M;
	for (int i = 0; i < M; i++) {
		int x, y;
		cin >> x >> y;
		if (find(x) == find(y))cout << "O";
		else cout << "X";
	}

	return 0;
}

왕이 갯수를 들고있도록 만든다

#include <iostream>
using namespace std;

int myBoss[10];
int getCnt[10];
int N, M;
int find(int n) {
	if (myBoss[n] == 0) {
		return n;
	}
	return myBoss[n] = find(myBoss[n]);
}
void setUnion(int t1, int t2) {
	int a = find(t1);
	int b = find(t2);
	if (a == b)return;
	myBoss[b] = a;
	//숫자를 넘겨준다 보스에게
	getCnt[a] += getCnt[b];
	getCnt[b] = 0;

}
int getCount(int num) {
	int ret = find(num);
	return getCnt[ret];
}
int main() {
	freopen_s(new FILE*, "input.txt", "r", stdin);
	//1 2 9 가 소속된 멤버 수
	cin >> N;
	for (int i = 0; i < 10; i++) {
		getCnt[i] = 1;
	}
	for (int i = 0; i < N; i++) {
		int a, b;
		cin >> a >> b;
		setUnion(a, b);
	}
	cin >> M;
	for (int i = 0; i < M; i++) {
		int x;
		cin >> x;
		cout <<getCount(x) << " ";
	}

	return 0;
}

함수로 빼서 만든당.

조직 갯수