随笔 - 87  文章 - 279  trackbacks - 0
<2006年9月>
272829303112
3456789
10111213141516
17181920212223
24252627282930
1234567

潜心看书研究!

常用链接

留言簿(19)

随笔分类(81)

文章分类(89)

相册

ACM OJ

My friends

搜索

  •  

积分与排名

  • 积分 - 211615
  • 排名 - 116

最新评论

阅读排行榜

评论排行榜

#include  < iostream >
using   namespace  std;

const   int  MAXN  =   100 ;

class  UFset
{
public :
    
int  parent[MAXN];
    UFset();
    
int  Find( int );
    
void  Union( int int );
}
;

UFset::UFset()
{
    memset(parent, 
- 1 sizeof (parent));
}


int  UFset::Find( int  x)
{
    
if  (parent[x]  <   0 )
        
return  x;
    
else
    
{
        parent[x] 
=  Find(parent[x]);
        
return  parent[x];
    }
//  压缩路径
}


void  UFset::Union( int  x,  int  y)
{
    
int  pX  =  Find(x);
    
int  pY  =  Find(y);
    
int  tmp;
    
if  (pX  !=  pY)
    
{
        tmp 
=  parent[pX]  +  parent[pY];  //  加权合并
         if  (parent[pX]  >  parent[pY])
        
{
            parent[pX] 
=  pY;
            parent[pY] 
=  tmp;
        }

        
else
        
{
            parent[pY] 
=  pX;
            parent[pX] 
=  tmp;
        }

    }

}


int  main()
{
    
return   0 ;
}
有bug请指正:)
posted on 2006-08-16 20:22 阅读(878) 评论(5)  编辑 收藏 引用 所属分类: 算法&ACM

FeedBack:
# re: 新学了并查集, 不知道能不能用呢^_^ 2006-08-17 11:55 Optimistic
强~
  回复  更多评论
  
# re: 新学了并查集, 不知道能不能用呢^_^ 2006-08-23 08:57 cainiao
终于知道并查集了
....
谢....  回复  更多评论
  
# re: 新学了并查集, 不知道能不能用呢^_^ 2006-09-01 09:46 small-fat
呵呵,我也学一下..  回复  更多评论
  
# re: 新学了并查集, 不知道能不能用呢^_^ 2006-09-01 23:15 踏雪赤兔
写法严谨,但不够简洁。不适合作为acm标程使用。
parent[]数组是两用的。定义如下
if(parent[i]>=0) parent[i]是父结点编号
else i是根且-parent[i]是集合规模  回复  更多评论
  
# re: 新学了并查集, 不知道能不能用呢^_^ 2006-09-01 23:20 
你意思是再加个 int size(int i)函数返回 i所在集合大小?  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理