Union Find

基于数组建立的数据结构，用于处理一些不交集（Disjoint Sets）的合并及查询问题

问题描述: 有N个元素，每个元素属于某个集合，之后进行对集合的多次合并和查询

维护一个长为N的father数组，father[i]表示第i个元素所属的集合

初始化

一开始将每个元素设为一个单元集合，即father[i]=i

void init(vector<int>& father) {
    for (int i = 0; i < father.size(); i++)
        father[i] = i;
}

查询

查询时一直沿father[i]向上回溯，直到father[i]==i为止，此时的i即是该集合的编号

这里要注意，如果路径比较长，这里的复杂度最高可以到O(N)，因此要进行路径的压缩，操作也很简单，在到达终点前，将路径上的每个点都直接指向根

在完成这样一次find后，father[i]一定是根节点，也就是路径变成每个点都和根直接相连

int find(vector<int>& father, int num) {
    if (num != father[num])
        father[num] = find(father, father[num]);
    return father[num];
}

合并

int merge(vector<int>& father, int num1, int num2) {
    int f1 = find(father, num1), f2 = find(father, num2);
    father[num1] = father[f1] = f2;
}

例题