三个月算法进阶--day83

2020-11-14 约 266 字预计阅读 1 分钟次阅读

动态连通性

触点，连接，连通分量，查找所在分量的标志符（find），是否属于相同的集合（connected ），归并集合（union）

以触点为索引的id[]数组

由给定的触点和链接找到根触电，连接两个根触点

总是将较小的树连接到较大的树，sz[]数组保存由触点索引的各个根节点所对应的分量大小，log n

扁平化树，find将路径遇到的所有节点直接链接到根节点

元素的分组管理问题（亲戚问题），集合（帮派）、集合的代表（帮主），路径压缩、按秩合并