The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

并查集模板

//////////////////////////////////////////////////////////////
//                        并查集模板                            //
//                                By abilitytao                //
//                                2009年7月6日                //
//////////////////////////////////////////////////////////////


int f[1001];//这里的1001只是一个示意性的数字 代表初始状态下的分支数目
int r[1001];
//由于不知道应该将子树挂到那个集合上面去,故需要一个准则,这里的准则是将子树挂到
//r值大的集合上面去,初始状态下r数组的值均为一,代表每个分支下只有一个数字

            



int find(int n)
{
    
if(f[n]==n)
        
return n;
    
else
        f[n]
=find(f[n]);
    
return f[n];
}
//查找函数,并压缩路径


int Union(int x,int y)
{
    
int a=find(x);
    
int b=find(y);
    
if(a==b)
        
return 0;
    
else if(r[a]<=r[b])
    
{
        f[a]
=b;
        r[b]
+=r[a];
    }

    
else
    
{
        f[b]
=a;
        r[a]
+=r[b];
    }

    
return 1;
    
}
//合并函数,如果属于同一分支则返回0,成功合并返回1

posted on 2009-07-06 20:05 abilitytao 阅读(585) 评论(0)  编辑 收藏 引用


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