京 东 价：
[定价：￥]
PLUS会员专享价
支　　持：
重　　量：
搭配赠品：
选择套装：
服务支持：
加载中，请稍候...
加载中，请稍候...
加载中，请稍候...
数据结构与算法分析：C语言描述（原书第2版）
商品介绍加载中...
扫一扫，精彩好书免费看
京东商城向您保证所售商品均为正品行货，京东自营商品开具机打发票或电子发票。
凭质保证书及京东商城发票，可享受全国联保服务（奢侈品、钟表除外；奢侈品、钟表由京东联系保修，享受法定三包售后服务），与您亲临商场选购的商品享受相同的质量保证。京东商城还为您提供具有竞争力的商品价格和，请您放心购买！
注：因厂家会在没有任何提前通知的情况下更改产品包装、产地或者一些附件，本司不能确保客户收到的货物与商城图片、产地、附件说明完全一致。只能确保为原厂正货！并且保证与当时市场上同样主流新品一致。若本商城没有及时更新，请大家谅解！
权利声明：京东上的所有商品信息、客户评价、商品咨询、网友讨论等内容，是京东重要的经营资源，未经许可，禁止非法转载使用。
注：本站商品信息均来自于合作方，其真实性、准确性和合法性由信息拥有者（合作方）负责。本站不提供任何保证，并不承担任何法律责任。
印刷版次不同，印刷时间和版次以实物为准。
价格说明：
京东价：京东价为商品的销售价，是您最终决定是否购买商品的依据。
划线价：商品展示的划横线价格为参考价，该价格可能是品牌专柜标价、商品吊牌价或由品牌供应商提供的正品零售价（如厂商指导价、建议零售价等）或该商品在京东平台上曾经展示过的销售价；由于地区、时间的差异性和市场行情波动，品牌专柜标价、商品吊牌价等可能会与您购物时展示的不一致，该价格仅供您参考。
折扣：如无特殊说明，折扣指销售商在原价、或划线价（如品牌专柜标价、商品吊牌价、厂商指导价、厂商建议零售价）等某一价格基础上计算出的优惠比例或优惠金额；如有疑问，您可在购买前联系销售商进行咨询。
异常问题：商品促销信息以商品详情页“促销”栏中的信息为准；商品的具体售价以订单结算页价格为准；如您发现活动商品售价或促销信息有异常，建议购买前先联系销售商咨询。
加载中，请稍候...
加载中，请稍候...
加载中，请稍候...
加载中，请稍候...
加载中，请稍候...
加载中，请稍候...
加载中，请稍候...
浏览了该商品的用户还浏览了
加载中，请稍候...
七日畅销榜
新书热卖榜
iframe(src='///ns.html?id=GTM-T947SH', height='0', width='0', style='display: visibility:')随笔- 509&
评论- 148&
&&&&&&&&&&&&&
　　&并查集&，英文名为&union-find set&，从名字就能看出来它支持合并与查找功能。另外还有一个名字叫&disjoint set&，中文名叫不相交集合。可能我们倾向于用最短的名字，所以就出现了&并查集&翻译为&disjoint set&的情况。并查集是一种树形结构，但与之前讲的树不同的是，这里的树节点只记录父节点，因此是一对一的，就可以用数组来表示并查集。
　　并查集可以认为是一个&森林&，也就是多棵树：
　　既然是并查集，先看看合并3和5之后结果如何：
　　那么3和5岂不是父子关系了？不是。我们关心的不是谁是父谁是子，而是3和5现在在一起了。下面这样效果是一样的：
　　这个看起来不像树形结构啊？那就来个节点个数更多的例子：
　　再看看查找操作：
　　这样的查找操作不改变树的形状，自底向上，复杂度必然是O(H)，也就是和树的高度成正比。有什么坏处呢？
　　路径压缩可以通过让树变得更扁来降低高度，从而加速查找操作。首先仍然是查找：
　　　　然后依次把沿路的所有节点直接挂到根节点上：
　　图片占的篇幅更少，显然是因为树变矮了。现在查找操作只需要O(1)时间了。
　　那么并查集有什么用呢？通俗地说，是用来判断一群人中，谁和谁是一伙儿的，谁和谁不是。不通俗地说，可以看看&等价关系&、&等价类&的一些集合论的资料，从中寻找一些理论支持。
　　在此给出一道用并查集解决的ZOJ简单题：
1 // My implementation for
disjoint set.
2 #include &vector&
3 using namespace
5 int findRoot(const vector&int& &dj, int x)
while (r != dj[r]) {
r = dj[r];
while (k != r) {
x = dj[x];
24 void unionSet(vector&int& &dj, int x, int y)
int n = (int)dj.size();
if (x == y) {
findRoot(x);
36 int main()
&posted on
阅读(...) 评论()}