유니온 파인드[Union Find]

유니온 파인드(Union Find)

 

그래프 알고리즘의 일종으로서 서로소 집합, 상호 배타적 집합(Disjoint-set)이라고도 한다. 

알고리즘 문제 풀이에서는 주로 집합을 나타내며 합집합만 사용할 때 쓰인다. 여러 노드가 존재할 때, 선택한 두 노드를 같은 그래프로 합치거나 서로 같은 그래프에 속하는지 판별하는 알고리즘이다. 

 

Parent[x] : x의 부모 노드 

Find : x가 속한 집합의 root 노드를 반환하는 연산

Union : x와 y가 포함되어 있는 집합을 합치는 연산

 

Parent 초기화

vector<int> parent(n);
for (int i = 0; i <= n; ++i) {
		parent[i] = i;
}

초기화, 최초 노드는 자기 자신을 루트 노드로 가진다.

Find

//Find

int myfind(int x) {
	if (parent[x] == x) 
		return x;
	else 
		return myfind(parent[x]);
}

기본적인 구현 : 부모를 향해서 계속 올라가다 자신과 부모가 같을 경우 리턴. 

연산속도 = O(N)

Union

//union
void myunion(int x, int y) {
	x = myfind(x);
	y = myfind(y);
	parent[y] = x;
}

기본적인 구현 : y의 부모를 x로 만든다. 

연산속도 = 평균적으로 O(logN)이지만, 트리 형성과정에서 오름차순 또는 내림차순인 사향트리(Skewed Tree)가 될 수 있으며 이 경우 시간복잡도는 O(N)이 되어버린다.

 

 

연산 속도를 높이기 위해 경로 압축과 랭크는 필수

// 경로 압축

int myfind(int x) {
	if (parent[x] == x) 
		return x;
	else 
		return parent[x] = myfind(parent[x]);
}

경로 압축
파인드는 루트를 찾는 연산이므로 같은 집합에 있는지 아닌지가 중요함. (트리를 만들기 위해서가 아님)
-> 부모 자식 관계는 중요하지 않음(단지 유니온 연산을 하다가 나온것)
-> 하나로 묶여 있다는것이 중요함.
-> 가장 중요한것은 루트.
최종 루트를 찾을 경우 루트를 전부 바꿔준다.

//랭크
void myunion(int x, int y) {
	x = myfind(x);
	y = myfind(y);
	if (x == y) 
		return;

	if (ranking[x] < ranking[y]) swap(x, y);
	parent[y] = x;
	if (ranking[x] == ranking[y]) {
		ranking[x] = ranking[y] + 1;
	}
}

랭크

Union을 구현할 때, 트리의 랭크를 기준으로 하여 더 작은 집합을 더 큰 집합의 자식으로 한다. 

(트리의 높이는 경로 압축을 사용하면 높이가 달라지기 때문에 랭크라고 표현한다.)

 

코드를 추가 해 주면 속도가 매우 빨라진다..

연산의 시간복잡도는 O(α(N))으로 상수라고 생각하면 된다.

α(N)은 아커만 역함수(Inverse Ackermann Function)로, N이 2^65536일때 α(2^65536)==5이므로 상수의 시간복잡도라고 생각하자. 

 

문제풀이

1717 집합의 표현 https://www.acmicpc.net/problem/1717

#include <iostream>
#include <vector>
using namespace std;

vector<int> parent(1000001);
vector<int> ranking(1000001);

int myfind(int x) {
	if (parent[x] == x) 
		return x;
	else 
		return parent[x] = myfind(parent[x]);
}

void myunion(int x, int y) {
	x = myfind(x);
	y = myfind(y);
	if (x == y) 
		return;

	if (ranking[x] < ranking[y]) swap(x, y);
	parent[y] = x;
	if (ranking[x] == ranking[y]) {
		ranking[x] = ranking[y] + 1;
	}
}


int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int n, m;
	cin >> n >> m;
	for (int i = 0; i <= n; ++i) {
		parent[i] = i;
	}

	for (int i = 0; i < m; ++i) {
		int cal, num1, num2;
		cin >> cal >> num1 >> num2;
		if (cal == 0) {
			myunion(num1, num2);
		}
		else {
			if (myfind(num1) == myfind(num2))
				cout << "YES\n";
			else
				cout << "NO\n";
		}
	}

}

2606 바이러스 https://www.acmicpc.net/problem/2606
1번 컴퓨터와 같은 집합인 컴퓨터가 몇 대인지 확인하는 문제

주의할 점은 부모가 같은지 체크하는 부분은 
f (parent[a] == parent[b]) 
가 아니라 
if (myfind(a) == myfind(b))
으로 해야된다.

2,3을 합치고 1,2를 합친 상태에서 

parent 배열의 값이 1,1,2이기 때문,,
findParent(3)을 해주어야 1,1,1으로 부모가 갱신됨
계속 갱신되어 있는 상태가 아니라, find 하면서 갱신되기 때문.

#include <iostream>
#include <vector>
using namespace std;

vector<int> parent(1000001);
vector<int> ranking(1000001);

int myfind(int x) {
	if (parent[x] == x) 
		return x;
	else 
		return parent[x] = myfind(parent[x]);
}

void myunion(int x, int y) {
	x = myfind(x);
	y = myfind(y);
	if (x == y) 
		return;

	if (ranking[x] < ranking[y]) swap(x, y);
	parent[y] = x;
	if (ranking[x] == ranking[y]) {
		ranking[x] = ranking[y] + 1;
	}
}


int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; ++i) {
		parent[i] = i;
	}

	for (int i = 0; i < m; ++i) {
		int num1, num2;
		cin >> num1 >> num2;
		myunion(num1, num2);
		
	}
	int ans = 0;

	for (int i = 2; i <= n; ++i) {
		if (myfind(i) == myfind(1)) ans++;
	}
	cout << ans;
}