并查集
一般用来做连通块问题
- 路径压缩
- 按轶合并（深度/子树大小）
扩展域并查集
P1892 [BalticOI 2003] 团伙
扩展域可以解决 [敌人的敌人是朋友] 这种关系
每个人有两个点 \(u,u+n\)，如果 \(u,v\) 是朋友，那么连接 \((u,v),(u+n,v+n)\)，否则连接 \((u,v+n),(v,u+n)\)
\(u+n\) 表示 \(u\) 的敌人集合
还可以判断二分图
带权并查集
P1196 [NOI2002] 银河英雄传说
维护联通性的时候顺便维护一些别的值