[PS] Union-Find

Union-Find 개념

Union-Find 자료구조는 그룹핑하여 자료를 저장하고, 같은 그룹인지 확인할 때, O(logN) 시간 만에 확인이 가능하다.

10의 최종보스가 8의 최종 보스 밑으로 들어간다!

기본 코드

#include <iostream>
using namespace std;

int arr[5] = { 0,0,1,2 };

// 조직의 최종보스를 리턴 함
int find(int n)
{
	if (arr[n] == 0) return n;
	int ret = find(arr[n]);
    arr[n] = ret; // 경로 압축 : return 하면서 직송상관을 보스로 바꾸기 -> 속도 업
	return ret;
}

// t2의 보스가 t1의 보스 밑으로 들어감
int setUnion(int t1, int t2)
{
	int a = find(t1); // t1의 최종보스
	int b = find(t2); // t2의 최종보스

	if (a == b) return;
	arr[b] = a;
}

int main() {
	setUnion(2, 3);

	return 0; 
}

그룹 개수 구하기

그룹 개수를 구하기 위해서는 기본 코드에서 살짝만 변화를 주면 된다.

int cnt = 0;

int setUnion(int t1, int t2)
{
	// 신규로 등장하는 애가 있으면 cnt++
    cnt++;
    
	int a = find(t1); // t1의 최종보스
	int b = find(t2); // t2의 최종보스

	if (a == b) return;
	arr[b] = a;
    
    // 그룹핑 성공하면 cnt--
    cnt--;
}

Cycle 유무 확인방법

Cycle 유무를 판단하기 위해서는 제약사항이 존재한다. 단방향그래프는 Cycle 판별 불가, 양방향그래프만 Cycle 판별 가능

cycle 유무 판별 또한 위의 기본코드에서 다음코드로 일부 수정해주면 된다.

int main() {
	setUnion(2, 3);

	int a,b;
    cin >> a >>b;
    if(find(a) == find(b))
    {
    	cout << "CYCLE 발견\n";
    	return 0;
    }
	setUnion(a,b);
    
    cout << "CYCLE 없음\n";
	return 0; 
}