[알고리즘] 유니온-파인드(Union-Find)

https://www.geeksforgeeks.org/introduction-to-disjoint-set-data-structure-or-union-find-algorithm/

Introduction to Disjoint Set (Union-Find Algorithm) - GeeksforGeeks

 

Disjoint-Set (서로소 집합 자료구조)를 구현할 때 쓰이는 알고리즘이다.

서로 공통 원소를 가지지 않는 부분 집합을로 나눠진 원소들에 대한 자료구조이다.

 

주로 최소 신장트리를 만드는 크루스칼 알고리즘과 같이 쓰인다.

 

집합 문제나 그룹 문제에도 사용된다.

 

배열과 트리를 사용한다.

배열: parent[]라는 배열을 사용하여 부모 노드를 담는다. i번째 요소는 i번째항목의 부모를 만든다.

 

트리: 두 요소가 같은 트리에 있으면, 그들은 같은 서로소 집합에 있는 것이다. 각 트리의 루트 노드는 집합의 대표자로 불린다.

 

 

두 연산

1.Find - 어떤 원소가 어느 집합에 속해있는지 찾는다.

2.Union - 두 집합을 하나로 찾는다.

 

1.Find

부모 노드까지 올라가 탐색한다. O(n)의 시간복잡도를 가진다.

// Finds the representative of the set
// that i is an element of

#include<bits/stdc++.h>
using namespace std;

int find(int i)

{

	// If i is the parent of itself
	if (parent[i] == i) {

		// Then i is the representative of
		// this set
		return i;
	}
	else {

		// Else if i is not the parent of
		// itself, then i is not the
		// representative of his set. So we
		// recursively call Find on its parent
		return find(parent[i]);
	}
}

// The code is contributed by Nidhi goel

 

2.Union - 두 요소를 묶는다. 한 요소의 자신이 속한 집합의 루트 요를가 다른 한 요소의 자식으로 만든다.

// Unites the set that includes i
// and the set that includes j

#include <bits/stdc++.h>
using namespace std;

void union(int i, int j) {

	// Find the representatives
	// (or the root nodes) for the set
	// that includes i
	int irep = this.Find(i),

	// And do the same for the set
	// that includes j
	int jrep = this.Find(j);

	// Make the parent of i’s representative
	// be j’s representative effectively
	// moving all of i’s set into j’s set)
	this.Parent[irep] = jrep;
}