并查集

提供两种操作

• find(x) -> 返回x所属的集合的id
• union(x, y) -> 将x和y所属的集合合并起来

优化手段

• path compression -> 优化find(x) -> O(1)
• union depends on rank -> 优化union(x, y) -> 减少path compression的次数

实现模版

684. 冗余连接

765. 情侣牵手