第二十三天(并查集)

今天完成题目:547,399,947 547:朋友圈

• N名学生N个集合

• 互为朋友的学生合并集合

399:除法求值

• 每个集合父结点与子结点的边为权重

• find返回从结点与父结点的比值

• union的时候,传入两个结点的比值,从而获得新父亲结点与原父亲结点的比值

• answer通过查找有无共同父亲来判断有无结果,并将两个结点与父结点的比值相除得到结果.

947:移除最多的同行或同列石头

• 将每个点压缩为一维的,x=x,y=10000+y

• 每个stones坐标表示将x与y合并起来

• 合并后的集合数,即为图中的连接子树数量

• 结点数-连接子图数量=结果

• 结果在图上的意义为所有连接子图(非环)的边数量