Union Find構造

1.反発セットとUnionFind構造
Union Find構造を表示する前に,反発集合について議論する.反発集合とは,各集合が共通要素を持たない集合を指す.反発集合中の要素の情報を格納し操作する資料構造はUnion-Find資料構造である.後述するunion関数とfind関数がサポートされるため、union-poind資料構造と呼ばれます.
2.ユニオンシード構造の3つの関数

初期化:n個の要素を初期化し、各セットに含める.

ルックアップ(find)演算:要素aが与えられたときに、その要素が属する集合のルートの演算を返す.(ツリーとルートが1対1であるため、見つかったルートは要素が属する集合を表します.)

連結演算:2つの要素a、bが与えられたときに、それらが属する集合を互いに連結する演算.

3.関連コード
3.1初期化関数
各要素のルートを自己に初期化します.

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

3.2 Find関数
親[u]は、uの親ノードではなくルートノードを格納することによってfind(u)が呼び出されるとすぐにルートノードに戻る.これをパス圧縮最適化(Path Compression Optimization)と呼びます.

int find(int u){
   	if(u==parent[u])
    	   return u;
        return parent[u]=find(parent[u]);
   }

3.3 Union関数
2つの要素u,vが与えられると、find関数によって2つの要素が属する集合のルートが検索されます.2つの値が同じ場合は、同じセットに属しているため、関数を終了します.2つの値が異なる場合、ルートの値は1つの小さなセットに別のセットを含みます.

void union(int u,int v){
   	u=find(u);v=find(v);
    	if(u==v)
    		return;
        if(u>v)
        	swap(u,v) 
        parent[v]=u;
   }

4.Union-Find構造全体コード

struct DisjointSet{
	vector<int> parent;
    
    //1. parent 초기화
    DisjointSet(int n): parent(n){
    	for(int i=0;i<n;i++)
        	parent[i]=i;
   }
   // 2. 루트 노드를 찾는 함수. 이때 경로 압축 기법을 사용한다.
   int find(int u){
   	if(u==parent[u])
    	   return u;
        return parent[u]=find(parent[u]);
   }
   
   // 3. 두 트리를 합치는 함수. rank를 활용한 개선된 방법도 있으나 기본적인 방법을 사용하겠음.
   void union(int u,int v){
   	u=find(u);v=find(v);
    	if(u==v)
    		return;
        if(u>v)
        	swap(u,v) // 두 트리 중 루트의 숫자가 작은 것이 합친 트리의 루트가 될 수 있게끔 하기 위함.
        parent[v]=u;
   }
};    

5.いつ使いますか.
グラフィックタイプでループの存在を決定するために使用
最も代表的なのはMSTアルゴリズムの中のクルーズアルゴリズムがツリーが拡張時にループが発生するかどうかを決定する際にUnion Find構造を用いたことである.
6.時間の複雑さ
find関数は呼び出すたびに実行時間が変更されるため、分割支払(?)が分析されます.また,実行ごとに必要とされる平均時間はO(a(n))である.a(n)は앵커만 상수と呼ばれる関数であり、すべてのサイズのnにとって4未満の値である.つまり一定時間が必要です.
結論:O(1)の時間的複雑さ
参考資料
アルゴリズムトラブルシューティングポリシー(本いっぱいから)