力扣:图之并查集问题

1.990. 等式方程的可满足性,算是比较基本的并查集问题了。

2.1202. 交换字符串中的元素,对可交换pair中构建并查集,用map分别排序,之后再遍历赋值,绝了。

3.684. 冗余连接,没想到用并查集,将边的两点合并,冗余边是已经在同一个集合中的。

4.959. 由斜杠划分区域,构造2*2的单元格,根据/单元格内合并,单元格间合并不需要讨论;计算连通集个数初始化为所有点,随着merge做--操作。

5.1631. 最小体力消耗路径,将矩阵视为图,计算边权重,并排序,将最小的边一次加入,判断00和m*n-1是否连通。

6.778. 水位上升的泳池中游泳,将t映射到坐标,遍历时刻t,将其对应的时刻,并且上下左右满足时刻的点合并,判断0和n*n-1坐标之间的连通性。

7.399. 除法求值,挺难的,将除法关系映射为有向边,结果为边的权重,在find的时候压缩路径,那么到新父节点的权重=到原来父节点的权重*新父节点的权重;在合并的时候考虑平行四边形的乘积相等,计算出旧根节点到新根节点之间的权重;查询时,肯定能压缩到根节点,就直接find相除得出结果。

原文地址:https://www.cnblogs.com/BlueBlueSea/p/14241473.html