[C++] 유니온 파인드(Union-Find)

유니온 파인드(Union-Find)

• 서로소인 집합들을 분할하여 저장한 집합
• Union(): 두 집합의 루트 부모를 합침
• Find(): 자신의 루트 부모를 찾아 계속해서 거슬러 올라가는 과정

 

유니온 파인드

 

문제

 

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

1717번: 집합의 표현

#include <iostream>
using namespace std;

int parent[1000001];

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

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

	if (b < a)
		parent[a] = b;
	else
		parent[b] = a;
}

int main()
{
	int n, m;
	cin >> n >> m;

	for (int i = 0; i <= n; ++i)
		parent[i] = i;

	while (m--) {
		int a, b, c;
		cin >> a >> b >> c;

		if (a == 0)
			Union(b, c);
		else {
			if (Find(b) == Find(c))
				cout << "YES\n";
			else
				cout << "NO\n";
		}
	}
}

 

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

4195번: 친구 네트워크

#include <iostream>
#include <map>
#include <string>
using namespace std;

map<string, int> m;
int parent[200001], cnt[200001];

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

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

	if (a != b) {
		parent[b] = a;
		cnt[a] += cnt[b];
		cnt[b] = 1;
	}
	return cnt[a];
}

int main() 
{
	int T, F;
	cin >> T;
	while (T--) {
		m.clear();
		for (int i = 1; i <= 200000; i++) {
			parent[i] = i;
			cnt[i] = 1;
		}

		cin >> F;
		int index = 1;
		for (int i = 0; i < F; i++) {
			string a, b;
			cin >> a >> b;
			if (m[a] == 0) 
				m[a] = index++;
			if (m[b] == 0) 
				m[b] = index++;

			cout << Union(m[a], m[b]) << "\n";
		}
	}
}