esc to dismiss

并查集

并查集的算法理解起来比较简单,一般用并查集来判断无向无环图的连通性。形象的应用例子就是找朋友。

并查集有两个操作: find 和 union

  • find: 查询元素的根节点

  • union: 将两个树合并,方法就是一棵树的根节点链接到另一棵树的根节点,这样两棵树就链接了

并查集的优化:压缩路径

x