Posted on 2010-08-10 11:36
MiYu 阅读(509)
评论(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;
}