题意:实现具有删除元素功能的并查集,注意删除x意味着仅仅删除x这一个结点,x若有子结点,子结点仍属原来集合。
这题做的都快哭了。。不过最后理解了并查集的删除,还是破涕为笑吧。。
比较难于叙述,关于删除还是参见这篇博文,写的很详细,使人顿悟~
Category Archives: 普通并查集
poj1456
这题并查集的用法非常巧妙。
思路:首先是贪心思想:按profit从大到小对这些产品进行排序,然后从pro[1]开始卖产品,对于产品pro[i],在距它的deadline最近的空的那天卖出,如果这一天是0,说明从pro[i].d到1这些天都已经被占用(一天只能卖出一件product),即这件产品无法被卖出。
用并查集优化:先算出最大的day,然后从0到day,每天都是并查集的一个元素。当连续的几天被占用的时候,把它们并入一个集合,根是这些被占用的连续的几天左边最近的未被占用的那天。如果根为0,说明这个product无法卖出。
但是这样贪心的正确性我还没有证明,求大神告知。
并查集资料
并查集的深化
hdoj1325
盯着网络流题看了半天还是不会做,好吧,还是做下并查集。
思路:首先把边当成无向边,保证无环,有环必不为树(并查集)。其次,保证只有一个点的入度为0,其他点的入度为1(设置数组)。最后还要满足连通(遍历并查集)。
注意两个地方:1.点的编号不一定连续。2.可能出现空树的case。
带权值的并查集
/* 根据不同题目的要求,merge()可以单独写,也可以并在main()中。 d[i]可以表示i与其父结点间的距离,当执行find(i)后,i的父亲会变成根(路径压缩),所以d[i]就变成了i到根的距离(当然其实也可以认为d[i]的意义没变,仍为i到其父节点的距离,因为路径压缩后,i的父节点就是根结点) 当然,这个域在具体题目中可以有更丰富的含义 注意:在合并时要保持两个集合的根的d[]属性正确。 */ #include<stdio.h> #include<stdlib.h> int find(int x) { if(bin[x]!=x) { int root=find(bin(x)); d[x]+=d[bin[x]]; return bin[x]=root; } else return x; } int main() { system("pause"); return 0; }
hdoj1116
开始思路想错了,想的太简单。无奈,,还是看了解题报告。。弱爆了,,发现原来是欧拉道路。。仔细想想,,原来这么简单。回头看看自己的程序,发现其实就是做了判欧拉道路的工作。于是加入并查集判连通的部分。
hdoj1272
链接:http://acm.hdu.edu.cn/showproblem.php?pid=1272
题目本身不难,但是一直WA,最后居然发现是因为早先自己写的并查集模版写错了,bin[fy]=fx;一句写成了bin[a]=b;。。。
改正后还是不能AC,,==!。无奈,最后还是看了discuss,发现有0 0 时输出Yes的case。。oh,my god~~
并查集样例
用并查集可以对无向图判环,每读入一条边,合并该边的两个顶点所在的集合,如果合并时两个顶点已经在一个集合中(说明已经有一条路径连通这两个顶点),则说明出现了环。
用并查集可以对有向图和无向图判连通性。