并查集

第二章 25分35秒

定义

1. 存储用户的输入的集合（比如 输入a b c d e 五个集合，每个集合含一种元素） 支持两种操作
2. issameset 判断两个输入是不是同一个集合

3. union 合并两个集合

   实现

4. 并查集可以采用链表来实现 不过issameset 时间复杂度高 如果用hashmap来实现 issameset很快（在 a的哈希表里查b） 合并很慢

5. 并查集采用了一种单指向的图的结构 如下图

issameset

• 找到两个输入他们的最顶层的元素 如果相同就是同一集合
• 优化：找最顶层元素的时候 会把路径上所有的元素 都直接指向顶级元素 如下图 b x y直接全部指向a

union

• 调用issameset 如果不在同一集合则合并 然后用小的顶级元素 直接指向大的顶级元素

  代码实现

  第二章 40分48秒