[笔记-数据结构]并查集

并查集是用来合并同一特征的元素、查找元素属于那个特征集合的数据结构
并查集有两个操作：合并集合，查找代表元
空间复杂度O(N)，合并的时间复杂度是查找的两倍，查找的时间复杂度为O(M Ackerman^-1(N))
（通俗的讲：Ackerman^-1(N)小于4，所以大概看成O(1)的算法好了）

模板

const int MAX=int(1e3);
struct Node{
    int parent, rank;//, data;
    Node(int parent=-1, int rank=0):
        parent(parent),rank(rank) {}
}node[MAX+5];
int find(int x){
// 查找代表元&路径压缩
    return (x==node[x].parent)?x:(node[x].parent=find(node[x].parent));
}

void join(int a, int b){
// 合并集合
    a=find(a); b=find(b);
    if (a==b) return;
    if (node[a].rank==node[b].rank) node[a].rank++;
    if (node[a].rank>node[b].rank) node[b].parent=a;
    else node[a].parent=b;
}

注意

1. 并查集的node数组需要提前初始化好
   node[i]=Node(i, 0)
   关键是parent初始为节点索引，且不能小于0（find()函数需要非负数）
   rank用于优化，设为0即可

根节点的维护

1. 维护根节点的数据最值
   在合并操作中对根节点进行判断，取最大或最小数据的节点作为新的根节点
   详情ZOJ-3261 Connections in Galaxy War 并查集 离线操作

2. 向上维护子节点的状态
   与线段树相似，在合并操作中加入PushUp来向上维护子节点的状态
   详情HDU-6109 数据分割 并查集（维护根节点）

例题

写的不多，如果有精彩的题目就放在这
入门题
POJ-2236 Wireless Network 并查集

进阶题
POJ-1182 食物链 并查集（互相关联的并查集写法）
ZOJ-3261 Connections in Galaxy War 并查集 离线操作
HDU-6109 数据分割 并查集（维护根节点）

> 18-03-21 Update：更新“根节点的维护”，加入两道例题