Posted on 2010-08-10 11:36
MiYu 閱讀(540)
評論(0) 編輯 收藏 引用 所屬分類:
ACM ( 并查集 ) 、
ACM ( MST 最小生成樹 )
MiYu原創, 轉帖請注明 : 轉載自 ______________白白の屋剛剛學習完并查集的基礎知識.. 自己寫了3個模板類 . 發上和大家分享下:
MiYu原創, 轉帖請注明 : 轉載自 ______________白白の屋
#include <iostream>
using namespace std;
typedef class arrUFS{
public:
arrUFS(int n = 0):N(n){ set = new int[n]; for ( int i = 0; i != N; ++ i) set[i] = i; };
~arrUFS(){ delete [] set; };
int find ( int x ){ return set[x]; }
void Merge1( int a,int b){ int i = min(set[a],set[b]);
int j = max(set[a],set[b]);
for ( int k=1; k<=N; k++) {
if (set[k] == j)
set[k] = i;
}
}
private:
int *set;
int N;
}arrUFS; // 數組形式
//樹形并查集, 路徑壓縮
typedef struct {
int parent;
int cnt;
}Tset;
typedef class treeUFS{
public:
treeUFS(int n = 0):N(n+2) { set = new Tset[N];
for ( int i = 0; i != N; ++ i)
set[i].parent = i,set[i].cnt = 1;
}
~treeUFS(){ delete [] set; };
int find ( int x ){ int r = x; while ( set[r].parent != r ) //循環結束，則找到根節點
r = set[r],parent;
int i = x;
while ( i != r) //本循環修改查找路徑中所有節點
{
int j = set[i].parent;
set[i].parent = r;
i = j;
}
return r;
}
void Merge1( int x,int y ){ x = find ( x ); y = find ( y );
if ( x == y ) return;
if ( set[x].cnt > set[y].cnt ){
set[y].parent = x;
set[x].cnt += set[y].cnt;
}
else{
set[x].parent = y;
set[y].cnt += set[x].cnt;
}
}
private:
int *set;
int N;
}treeUFS; // 樹形式 路徑壓縮
//屬性并查集, 帶樹深
typedef struct {
int parent;
int height;
}Tset;
typedef class treeUFS{
public:
treeUFS(int n = 0):N(n+2) { set = new Tset[N];
visited = new bool[N];
for ( int i = 0; i != N; ++ i)
set[i].parent = i,set[i].height = 1,visited[i] = false;
}
~treeUFS(){ delete [] set; };
int find ( int x ){ int r = x; while ( r != set[r].parent ) r = ser[r].parent;
return r;
}
void Merge1( int x,int y ){ x = find ( x ); y = find ( y );
if ( x == y ) return;
if ( set[x].height == set[y].height ){
set[y].parent = x;
set[x].height ++;
}
else if ( set[x].height < set[y].height ) {
set[x].parent = y;
}
else{
set[y].parent = x;
}
}
private:
int *set;
bool *visited;
int N;
}treeUFS; // 樹形式 帶樹深
int main ()
{
return 0;
}