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.一一对比,不同则不同构。

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也就可以一并解决了。