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 阅读(597) 评论(0)  编辑 收藏 引用


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