并查集和并查集

并查集的高级操作

维护并查集大小

siz[i]记录i节点所在集合的大小。

具体的做法是:

  • 在路径压缩回溯时,将当前节点的siz置为父节点的siz
  • 在合并两个集合的时候,要将合并之后集合的根节点的siz加上被合并的集合的siz,然后把被合并集合的siz置为合并后集合的siz
阅读更多
Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×