并查集解决什么问题

假设班上有若干同学，他们之间有一些“朋友关系”。朋友的朋友也是朋友，所以这些人会形成一个一个的小圈子。现在的问题是：

• 给定两个人，他们是不是同一个圈子的？
• 如果让两个人成为朋友，会不会把两个原本不相干的圈子合并成一个？

这种“判断元素是否属于同一集合”以及“合并两个集合”的问题，就是并查集（Union-Find，也叫 Disjoint Set Union，DSU）的专长。

经典应用场景包括：