数据结构-并查集

作者： 作者的头像   granite ,  2022-07-20 11:05:39 ,  所有人可见 ,  阅读 127

2


并查集

  1. 作用
    • 将两个集合合并
    • 询问两个元素是否在同一个集合中
  2. 基本原理
    • 每个集合用一棵树表示，树根的编号就是整个集合的编号，每个节点存储它的父节点，p[x]表示x的父节点
    • 判断树根：p[x] == x
    • 求x的集合编号：while (p[x] != x) x = p[x]
    • 合并两个集合：p[x] = y,x、y为两个集合的根节点
  3. 优化：路径压缩
    • 在x找到根节点后，将路径上所有点直接指向根节点

0 评论

1024
x