并查集

Union-Find algorithm

并查集（Union-Find Set）

数组

quick-find
quick-union
weighted-quick-union
depth-quick-union
path-compression-quick-union
path-compression-weighted-quick-union

union将两个集合的根结点连接
quick_union模板代码

union将一个集合的每个元素的groupid设置为另一个集合的groupid
quick_find模板代码

union找出两个集合的groupid元素；
然后根据两个集合的深度，判断连接方式，深度小的树挂在深度大的树 groupid下面
depth-quick-union模板代码

union将两个集合的根结点连接

路径压缩(path-compression)
Find时通过v[i] = v[v[i]]降低树的深度

union找出两个集合的groupid元素；
然后根据两个集合的大小，判断连接方式，小的树挂在大的树 groupid下面
weighted-quick-union