[PS] Union-Find

8724 ワード
ps テキストリンク

Union Findコンセプト


UnionFindデータ構造はパケット格納されており,同一グループであると判定された場合,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; 
}
データ構造とアルゴリズム——二叉木遍歴
手卑ででたらめを書いて見ないでください:生産者の消費者-同期の問題