UNION-FIND(并查集)

summary_2018/07 algorithm todo_(code)

1、日常工作

• UNION-FIND（并查集）

2、技术学习

• UNION-FIND（并查集）
  
  • 并查集（Disjoint set或者Union-find set）是一种树型的数据结构，常用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。
  • 两个基本操作：合并和查询
  • quick-find:p and q are connected iff they have the same id.
  • quick-union:To merge components containing p and q,set the id of p's root to the id of q's root.
  • (Improvement 1: weighting)Weighted quick-union:Balance by linking root of smaller tree to root of larger tree.
  • (Improvement 2: path compression路径压缩)：Just after computing the root of p,set the id of each examined node to point to that root
    

### Example
#### quick-find
#### quick-union
#### (Improvement 1: weighting)Weighted quick-union
#### (Improvement 2: path compression路径压缩)