hdoj3635

带权并查集,一开始不知道合并时被其他集合合并的集合的根节点的time[]怎么设置,后来想想其实只要直接设为1就行了,因为这个根节点肯定是第一次移动,否则就不可能是根节点了,囧。。
对于非根节点,它的移动次数可以用到根节点的距离表示,,因为每次询问Q x之前,都要先find(x),所以此时由于路径压缩,time[x]已经更新,所以可以保证正确。
开始由于a、b定义成char,RE多次。。。

hdoj3926

这题多写了个continue。。检查n久。。
由于只有两只手,所以:
1.若形成的图不连通,则几个连通分量或为环,或为链。
2.若形成的图连通,则或为环,或为链。
判断是否同构的步骤:
1,顶点数是否相同
2.并查集:把连通的点并入一个集合,同时更新权cnt[],用于表示集合元素个数。
3.在合并时注意判断是否形成环。(注意a b b a这种情况,这是不能认为是环)
4.将两个图的各个连通分量所含顶点数及其形状存入两个数组,进行排序
5.如果两个图的连通分量数不同,则不同构。
5.一一对比,不同则不同构。

poj1456

这题并查集的用法非常巧妙。
思路:首先是贪心思想:按profit从大到小对这些产品进行排序,然后从pro[1]开始卖产品,对于产品pro[i],在距它的deadline最近的空的那天卖出,如果这一天是0,说明从pro[i].d到1这些天都已经被占用(一天只能卖出一件product),即这件产品无法被卖出。
用并查集优化:先算出最大的day,然后从0到day,每天都是并查集的一个元素。当连续的几天被占用的时候,把它们并入一个集合,根是这些被占用的连续的几天左边最近的未被占用的那天。如果根为0,说明这个product无法卖出。
但是这样贪心的正确性我还没有证明,求大神告知。

hdoj3172

做这题其实是想复习一下map的用法,很久不用就忘了。。
map用clear()清空,用count()查找map中的关键字,找到返回1,否则返回0(也可以用find(),find()找到会返回关键字相应的迭代器,找不到返回end(),这里没必要)
注意读题,这题的输入很恶心,不仔细读题很难意识到是自己的数据读入方式错了,不过题目其实写的很清楚了,也不好埋怨它变态。。
7771494 2013-03-15 17:45:45 Accepted 3172 1359MS 2420K 1084 B C++ shadow
1359MS,速度不咋滴。。

poj1182——带权的并查集

哈哈,终于理解了带权的并查集,昨天想的差点崩溃。。其实本来心情就不好,再加上这个东东想不通,顿觉前途灰暗,了无生机,要学的太多,懂的太少。。不过还好网上有很多大牛写的心路历程,看了之后重新振作了精神。既然入门晚,起点已经输了,那么就不能输掉坚持了啊。。
好吧,闲话有点多了。这题看了网上许多解题报告,感觉作为带权并查集的入门题太合适了。
思路:最巧妙的地方是,把x和y是同类表示成x到y距离为0,把x吃y表示成x到y距离为1,把x被y吃表示成x到y距离为2.这样分别考虑各种情况你会发现,如果存在x-1->y-2->z,则x和z的关系是同类关系,这与x到z距离((1+2)%3)符合,这说明两者之间的关系可以用距离取模表示。这样如果两者在一个集合中,那么关系可以确定。
否则对于d x y,需要合并两个集合。具体思路见网上各种解题报告。。
本来想用迭代的方法写find(),不过感觉加了权不会写,就用了递归。
在递归返回的时候更新x点的权为到根结点的权,之后更改父节点为根节点(路径压缩),注意这两者的顺序不能反过来。在合并时必须保证两个集合根节点之间的距离正确,这样下次查找的时候路径压缩时的更新权值才能正确。
由于用到一个元素的时候一般要先执行find(x),所以可以保证这之后ch[x]已经表示的是x到根结点的距离。
这样,hdoj3047也就可以一并解决了。

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

开始思路想错了,想的太简单。无奈,,还是看了解题报告。。弱爆了,,发现原来是欧拉道路。。仔细想想,,原来这么简单。回头看看自己的程序,发现其实就是做了判欧拉道路的工作。于是加入并查集判连通的部分。

并查集样例

用并查集可以对无向图判环,每读入一条边,合并该边的两个顶点所在的集合,如果合并时两个顶点已经在一个集合中(说明已经有一条路径连通这两个顶点),则说明出现了环。
用并查集可以对有向图和无向图判连通性。