さらに(Union-Find)c++詳細を調べる
定義＃テイギ＃
ルックアップ・セットは、交差しないセット(Disjoint Sets)のマージおよびクエリーの問題を処理するツリー型のデータ構造です.よく使われているのは森で表されています
特長
1.「そして調査集」は「配列」に構築された木の構造であり、この木は子供の結点が父親の結点を指している.2.「そして調査集」は主に「連通性」の問題を解決するために用いられ、重点的に注目しているのは私とあなたが友达かどうかですが、私たちはいくつかの友达の関係で、重要ではありません.3.「并查集」は木なので、最適化の戦略は依然として木の高さと力比べで、最適化の考え方は「ランクによる合并」と「経路圧缩」がある.
第1版(idベースのパラレルセット)
第2版(parentベースのパラレルセット)
第3版(sizeベースの最適化)
第4版(rankベースの最適化)-一般的
i番目の要素をルートとするツリーの高さを表すrank配列を導入した.
第5版(パス圧縮に基づく非再帰的実装(共通))
この版のコードは最も多く使われている.分かりやすく、コード量が少ないからです.
この文を理解するだけでparent[p]=parent[parent[p]];これを「隔世圧縮」と呼ぶことができる.
圧縮は徹底していないが、複数回圧縮しても完全圧縮の効果が得られ、再帰を使用せずに「再帰スタック」空間を占有する
ルックアップ・セットは、交差しないセット(Disjoint Sets)のマージおよびクエリーの問題を処理するツリー型のデータ構造です.よく使われているのは森で表されています
特長
1.「そして調査集」は「配列」に構築された木の構造であり、この木は子供の結点が父親の結点を指している.2.「そして調査集」は主に「連通性」の問題を解決するために用いられ、重点的に注目しているのは私とあなたが友达かどうかですが、私たちはいくつかの友达の関係で、重要ではありません.3.「并查集」は木なので、最適化の戦略は依然として木の高さと力比べで、最適化の考え方は「ランクによる合并」と「経路圧缩」がある.
第1版(idベースのパラレルセット)
namespace UF1 {
class UF {
public:
//
UnionFind(int n) {
count = n;
id = new int[n];
// , id[i] ,
for (int i = 0; i < n; i++)
id[i] = i;
}
//
~UnionFind() {
delete[] id;
}
// , p
int find(int p) {
assert(p >= 0 && p < count);
return id[p];
}
// p q
bool isConnected(int p, int q) {
return find(p) == find(q);
}
// p q
void unionElements(int p, int q) {
int pID = find(p);
int qID = find(q);
if (pID == qID)
return;
// ,
for (int i = 0; i < count; i++)
if (id[i] == pID)
id[i] = qID;
}
private:
int* id;
int count;
}
};
第2版(parentベースのパラレルセット)
namespace UF2{
class UnionFind{
private:
// Union-Find,
// parent[i] i
int* parent;
int count; //
public:
//
UnionFind(int count){
parent = new int[count];
this->count = count;
// , parent[i] ,
for( int i = 0 ; i < count ; i ++ )
parent[i] = i;
}
//
~UnionFind(){
delete[] parent;
}
// , p
// O(h) , h
int find(int p){
assert( p >= 0 && p < count );
// ,
// : parent[p] == p
while( p != parent[p] )
p = parent[p];
return p;
}
// p q
// O(h) , h
bool isConnected( int p , int q ){
return find(p) == find(q);
}
// p q
// O(h) , h
void unionElements(int p, int q){
int pRoot = find(p);
int qRoot = find(q);
if( pRoot == qRoot )
return;
parent[pRoot] = qRoot;
}
};
}
第3版(sizeベースの最適化)
namespace UF3{
class UnionFind{
private:
int* parent; // parent[i] i
int* sz; // sz[i] i
int count; //
public:
//
UnionFind(int count){
parent = new int[count];
sz = new int[count];
this->count = count;
for( int i = 0 ; i < count ; i ++ ){
parent[i] = i;
sz[i] = 1;
}
}
//
~UnionFind(){
delete[] parent;
delete[] sz;
}
// , p
// O(h) , h
int find(int p){
assert( p >= 0 && p < count );
// ,
// : parent[p] == p
while( p != parent[p] )
p = parent[p];
return p;
}
// p q
// O(h) , h
bool isConnected( int p , int q ){
return find(p) == find(q);
}
// p q
// O(h) , h
void unionElements(int p, int q){
int pRoot = find(p);
int qRoot = find(q);
if( pRoot == qRoot )
return;
//
//
if( sz[pRoot] < sz[qRoot] ){
parent[pRoot] = qRoot;
sz[qRoot] += sz[pRoot];
}
else{
parent[qRoot] = pRoot;
sz[pRoot] += sz[qRoot];
}
}
};
}
第4版(rankベースの最適化)-一般的
i番目の要素をルートとするツリーの高さを表すrank配列を導入した.
namespace UF4{
class UnionFind{
private:
int* rank; // rank[i] i
int* parent; // parent[i] i
int count; //
public:
//
UnionFind(int count){
parent = new int[count];
rank = new int[count];
this->count = count;
for( int i = 0 ; i < count ; i ++ ){
parent[i] = i;
rank[i] = 1;
}
}
//
~UnionFind(){
delete[] parent;
delete[] rank;
}
// , p
// O(h) , h
int find(int p){
assert( p >= 0 && p < count );
// ,
// : parent[p] == p
while( p != parent[p] )
p = parent[p];
return p;
}
// p q
// O(h) , h
bool isConnected( int p , int q ){
return find(p) == find(q);
}
// p q
// O(h) , h
void unionElements(int p, int q){
int pRoot = find(p);
int qRoot = find(q);
if( pRoot == qRoot )
return;
//
//
if( rank[pRoot] < rank[qRoot] ){
parent[pRoot] = qRoot;
}
else if( rank[qRoot] < rank[pRoot]){
parent[qRoot] = pRoot;
}
else{ // rank[pRoot] == rank[qRoot]
parent[pRoot] = qRoot;
rank[qRoot] += 1; // , rank
}
}
};
}
第5版(パス圧縮に基づく非再帰的実装(共通))
この版のコードは最も多く使われている.分かりやすく、コード量が少ないからです.
この文を理解するだけでparent[p]=parent[parent[p]];これを「隔世圧縮」と呼ぶことができる.
圧縮は徹底していないが、複数回圧縮しても完全圧縮の効果が得られ、再帰を使用せずに「再帰スタック」空間を占有する
namespace UF5{
class UnionFind{
private:
// rank[i] i
// , rank , rank ,
// rank height depth ,
int* rank;
int* parent; // parent[i] i
int count; //
public:
//
UnionFind(int count){
parent = new int[count];
rank = new int[count];
this->count = count;
for( int i = 0 ; i < count ; i ++ ){
parent[i] = i;
rank[i] = 1;
}
}
//
~UnionFind(){
delete[] parent;
delete[] rank;
}
// , p
// O(h) , h
int find(int p){
assert( p >= 0 && p < count );
// path compression 1
while( p != parent[p] ){
parent[p] = parent[parent[p]];
p = parent[p];
}
return p;
// path compression 2,
// if( p != parent[p] )
// parent[p] = find( parent[p] );
// return parent[p];
}
// p q
// O(h) , h
bool isConnected( int p , int q ){
return find(p) == find(q);
}
// p q
// O(h) , h
void unionElements(int p, int q){
int pRoot = find(p);
int qRoot = find(q);
if( pRoot == qRoot )
return;
//
//
if( rank[pRoot] < rank[qRoot] ){
parent[pRoot] = qRoot;
}
else if( rank[qRoot] < rank[pRoot]){
parent[qRoot] = pRoot;
}
else{ // rank[pRoot] == rank[qRoot]
parent[pRoot] = qRoot;
rank[qRoot] += 1; // , rank
}
}
};
}