[자료구조] Disjoint Set (Union-Find)

Disjoint Set

• 공통 원소가 없는 상호 배타적인 부분 집합 들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조
• 초기화 : N개의 원소가 각각의 집합에 포함되어 있도록 초기화
• 합치기 연산 : 두 원소가 주어질 때, 이들이 속한 두 집합을 하나로 합친다.
• 찾기 연산 : 어떤 원소가 주어질 때, 이 원소가 속한 집합을 반환

배열로 표현

• 합치기에서 두 집합을 합치기 위해선 배열의 모든 원소를 순회하며 집합 번호를 다른 집합 번호로 교체해야 한다. O(N)
• 찾기 연산에선 원하는 집합 번호를 바로 찾을 수 있다. O(1)

트리로 표현

• 초기화 : 모두 각자 다른 집합이 된다. 각 노드는 모두 루트 노드가 되며 N개의 루트 노드를 생성하고 자기 자신을 가리키는 포인터를 가진다.
• 합치기 : 각 트리의 루트를 찾은 뒤, 서로 다르다면 한 루트를 다른 루트의 자식으로 두어 합친다. 수행 시간이 찾기 연산과 비례한다.
• 찾기 : 각 노드에 저장된 포인터를 따라가 주어진 원소가 포함된 트리의 루트 노드를 찾는다. O(logN)

최적화

• 루트로 구현할 때, 최악의 경우 비대칭 트리가 발생하면 배열로 구현한 경우보다 비효율적으로 작동할 수 있다.
• 높이가 더 낮은 트리를 높은 트리 밑에 넣음으로써 해결한다.

코드

struct Node
{
	Node* parent;
};

class DisjointSet
{
public:
	DisjointSet(int n) : _parent(n), _rank(n, 1)
	{
		for (int i = 0; i < n; i++)
			_parent[i] = i;
	}

	int Find(int u)
	{
		if (u == _parent[u])
			return u;

		return _parent[u] = Find(_parent[u]);
	}

	// u와 v를 합친다 (일단 u가 v 밑으로)
	void Merge(int u, int v)
	{
		u = Find(u);
		v = Find(v);

		// 서로 다른 그룹
		if (u == v)
			return;

		if (_rank[u] > _rank[v])
			::swap(u, v);

		// rank[u] <= rank[v] 보장됨
		_parent[u] = v;
		if (_rank[u] == _rank[v])
			_rank[v]++;

		_parent[u] = v;
	}

private:
	vector<int> _parent;
	vector<int> _rank;
};