并查集

定义

并查集是一种用于管理元素所属集合的数据结构，实现为一个森林，其中每棵树表示一个集合，树中的节点表示对应集合中的元素。

采用树的形式维护所有集合，树根的编号就是整个集合的编号。

对于每一个节点 \(i\)，我们存储 \(p_i\) 为它的父亲节点。

最开始，对于所有 \(i \in [1, n]\)，有 \(p_i = i\)，也就是最开始所有数各属于一个集合。因此就有如果 \(i\) 点是一棵树的祖宗节点，那么 \(p_i = i\)。

那如果想要知道 \(i\) 节点的祖宗节点，那么可以先找到它的父亲节点，再找到它父亲节点的父亲节点……最后如果 \(p_i = i\)，则代表找到了根节点。

int find(int x){
    if(p[x] == x){      // 如果找到了祖宗节点，直接返回
        return x;
    }
    return find(p[x]);  // 否则查找它的父亲节点
}

时间复杂度大约 \(\Theta(1)\)

如果我们改变 \(p_i\) 的定义，使得 \(p_i\) 为 \(i\) 号点的祖宗节点，那么以后查询时就不需要一遍一遍地查找祖宗节点了。

因此，在查找祖宗节点的过程中，如果遇到一个父亲节点，那么可以直接把这个父亲节点指向祖宗节点，即

int find(int x){
    if (p[x] == x){      // 如果找到了祖宗节点，直接返回
        return p[x];
    }
    p[x] = find(p[x]);  // 否则查找它的父亲节点，并将父亲节点也直接指向祖宗节点
}

如果要询问 \(i\) 和 \(j\) 元素是否在一个集合当中，那么只需要判断 \(find(i) = find(j)\) 即可。

时间复杂度 \(\Theta(1)\)

bool same_set(int x, int y){
    return find(x) == find(y);
}

如果要将两个集合合并，那么只需要在两颗树中插一条边即可，表示将两棵树合并为一棵树。

但是要更改集合的标号。即如果要将 \(i\) 号点所在的集合和 \(j\) 号点所在的集合合并，那么需要使 \(f_{find(i)} = find(j)\)，这个操作表示把 \(j\) 所在的树的根节点下插入一颗子树，这颗子树就是 \(i\) 节点所在的树。

void merge(int x, int y){
    p[find(x)] = find(y);
}