| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 592 人关注过本帖
标题:并查集合问题
只看楼主 加入收藏
mhchen2010
Rank: 1
等 级:新手上路
帖 子:6
专家分:0
注 册:2012-12-25
结帖率:0
收藏
 问题点数:0 回复次数:2 
并查集合问题
typedef struct node
{  int data;        //结点对应人的编号
   int rank;        //结点对应秩
   int parent;        //结点对应双亲下标
} UFSTree;            //并查集树的结点类型

void MAKE_SET(UFSTree t[]) //初始化并查集树
{  int i;
   for (i=1;i<=N;i++)
   {  t[i].data=i;    //数据为该人的编号
     t[i].rank=0;    //秩初始化为0
     t[i].parent=i;    //双亲初始化指向自已
   }
}




int FIND_SET(UFSTree t[],int x)   
//在x所在子树中查找集合编号
{  if (x!=t[x].parent)    //双亲不是自已
    return(FIND_SET(t,t[x].parent));
                   //递归在双亲中找x
   else
    return(x);        //双亲是自已,返回x
}








void UNION(UFSTree t[],int x,int y)
//将x和y所在的子树合并
{  x=FIND_SET(t,x);    //查找x所在分离集合树的编号
   y=FIND_SET(t,y);    //查找y所在分离集合树的编号
   if (t[x].rank>t[y].rank)//y结点的秩小于x结点的秩
    t[y].parent=x;     //将y连到x结点上,x作为y的孩子结点
   else            //y结点的秩大于等于x结点的秩
   {  t[x].parent=y;    //将x连到y结点上,y作为x的孩子结点
    if (t[x].rank==t[y].rank)    //x和y结点的秩相同
       t[y].rank++;    //y结点的秩增1
   }
}


1)t[x]的秩大于t[y]的秩,应该是y接到x上,怎么是x接到Y上呢

2)t[y].parent=x;     //将y连到x结点上,x作为y的孩子结点
我感觉这句话中的程序和解释说反了?
搜索更多相关主题的帖子: parent 
2013-07-03 15:09
holy__shit
Rank: 2
等 级:论坛游民
帖 子:21
专家分:55
注 册:2013-8-23
收藏
得分:0 
回复 楼主 mhchen2010
1.t[x] > t[y]则x > y   用小下标y
2.t[x] <= t[y]则 x <= y 用小下标x

羁绊太多,只会迷失自我!
2013-08-23 02:19
赵富强
Rank: 1
来 自:China
等 级:新手上路
帖 子:1
专家分:0
注 册:2016-11-6
收藏
得分:0 
2016-11-06 13:59
快速回复:并查集合问题
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.026562 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved