并查集

理论

并查集如其名，使用一个集合（数组）来完成合并和查询的操作，用于判断两个元素是否在同一个集合中。

• 合并（Unite）：合并两个集合所属的集合，将一个根节点指向另一个根节点。
• 查询（Find）：查询某个元素所属的集合或根节点。

并查集支持删除单个元素、移动或维护树上的边权，但不能以较低复杂度实现集合的分离。

实现

数组实现

通常使用维护一个数组以实现并查集，数组的索引表示元素的编号，值表示该元素的父节点。当值为本身时，该元素是一个集合的根节点。 该数组应该被初始化为-1或索引。

int parents[size_t];
for(int i=0;i<parents.size();i++){
    parents[i]=i;
}

使用untion()和find()方法进行加入和查询操作，其中find()方法通常用递归实现，以便路径压缩或其它优化。

int find(int x){
    //x为需要查询的节点
    if(parent[x]==x)return x;
    else return find(parent[x]);
}

void union(int x,int y){
    //x和y为两个需要合并到同一个集合的节点
    int rootx=find(x);
    int rooty=find(y);
    if(rootx!=rooty){
        parents[y]=rootx;
    }
}

路径压缩

通过在查询根节点时将不与根节点的直接相连的节点，直接指向根节点，以加速多次查询时的查询速度。 通常使用递归实现。

int find(int x){
    //x为需要查询的节点
    if(parents[x]==x)return x;
    else {
        parents[x]=find(parents[x]);
        return parents[x]
    }
}

启发式合并

启发式合并为解决查找的时间复杂度而诞生。 极端情况下，并查集可能退化为链，导致查找末端节点的根节点需要较高复杂度。启发式合并通过动态调整合并策略（选择左节点或右节点为根节点），能降低树高的增长速度，将查找时间压缩到O(logN)内。

启发式合并有按子元素数量大小合并和按秩合并。

在“按大小合并”中，要使树的高度增加 1，必须合并两棵大小相似的树（否则，高度取大树，即保持不变）。这意味着为了让高度达到 $h$，至少需要 $2^h$ 个节点。反之，拥有 $n$ 个节点的树，其高度最高为 $\log_2 n$。

模板题

冗余连接

无向图

题目链接：108. 多余的边

思路

根据题目可得，当两个节点已经有同一个根节点时，再连接这两条边就会形成环。 因此使用并查集，边输入边查，如果当前边的两个端点的根节点不同就合并，如果相同则当前边就是所需冗余边。

实现代码

点击展开代码

#include<iostream>
using namespace std;

//并查集
const int MAX = 1005;
int n;
int p[MAX];
int s, t;
int resX, resY;

int find(int x) {
    if (p[x] == x)return x;
    else {
        p[x] = find(p[x]);
        return p[x];
    }
}

void join(int x, int y) {
    int rootx = find(x);
    int rooty = find(y);
    if (rootx != rooty)p[rootx] = rooty;
}

bool isSame(int x, int y) {
    int rootx = find(x);
    int rooty = find(y);
    return rootx == rooty;
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++)p[i] = i;
    for (int i = 1; i <= n; i++) {
        cin >> s >> t;
        if (isSame(s, t)) {
            cout << s << " " << t;
            break;
        }

        join(s, t);

    }
    return 0;

}

有向树

题目链接：109. 多余的边II

思路

观察图可得，对于具有冗余边的有向树，会出现以下两种情况：

因此，我们可以在录入数据的同时记录入度。 即，使用vector<pair<int,int>> edges按顺序记录边，并开一个整型数组记录每个节点的入度。

读入数据后，根据是否存在入度为2的节点进行不同的判断。 对于入度均为1的有向环图，只要删掉其中一条即可，思路和无向图相同，并查集查找并删除即可； 对于存在入度为2的节点的图，可能存在只能删除特定边的情况，因此首先需要先遍历边数组，找出指向该节点的两条边，假设删除第二条边，用并查集检查删除后是否能形成有向树。如果能则第二条边就是答案，否则就是第一条边。

实现代码

点击展开代码

#include<iostream>
#include<vector>
using namespace std;

//存边并记录入度

//如果不存在出度为2的点，则表示形成了环
//使用并查集，遍历边数组，发现两点已在同一集合中时则为目标边

// 如果存在出度为2的点
//找到入度为2的点，遍历边数组并查找其父节点，按顺序记录
//尝试删除第二条边，并查集检查是否有环，有则删第一条，没有则删第二条

//s 父节点     t 子节点

const int MAX = 1005;
int n, s, t, de = -1;    //de：标记出度为2的节点，初始化为-1，如果没有就是环
int p[MAX], d[MAX];
vector<pair<int, int>> edges;
pair<int, int > du[2];

int find(int x) {
    if (p[x] == x)return x;
    else {
        p[x] = find(p[x]);
        return p[x];
    }
}

void join(pair<int,int> edge) {
    int father = edge.first;
    int child = edge.second;

    p[child] = father;
}

bool isSame(int x, int y) {
    int rootx = find(x);
    int rooty = find(y);
    return rootx == rooty;
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> s >> t;
        edges.push_back({ s,t });

        d[t] = d[t] + 1;
        if (d[t] > 1)de = t;
        p[i] = i;
    }

    if (de == -1) {
        //有向环
        for (auto edge : edges) {
            if (isSame(edge.first, edge.second)) {
                cout << edge.first << " " << edge.second;
                break;
            }
            join(edge);
        }

    }
    else {
        //入度>1
        int ind = 0;
        for (auto edge : edges) {
            if (edge.second == de){
                du[ind] = edge;
                ind++;
                }
            if (ind == 2)break;
        }

        //遍历边数组，尝试删除第二条
        for (auto edge : edges) {
            if (edge == du[1])continue;
            if (isSame(edge.first, edge.second)) {
                cout << du[0].first << " " << du[0].second;
                return 0;
            }
            join(edge);
        }

        cout << du[1].first << " " << du[1].second;

    }


    return 0;
}

链表合并

题目链接：码蹄集OJ-史莱姆融合

思路

并查集记录，以单个点表示当前已经融合的连续段（这里用最左点表示，即合并的时候以左段为父节点），同时更新记录。即，每次合并有以下三步：

• 合并并查集
• 更新当前段最左节点和最右节点
• 合并链表

由于并查集只能记录集合，而无法记录集合间元素的顺序，因此需要一个额外的链表来记录点的顺序。 此处用数组模拟，值为当前节点的下一个节点。

实现代码

点击展开代码

#include<iostream> 
using namespace std;

const int MAX = 1e6 + 5;
int p[MAX];
int n, x, y;
int nxt[MAX];

//当前段最左的节点和最右的节点
struct Point {
    int l;   //left
    int r;   //right
}points[MAX];

int find(int x) {
    if (p[x] != x)p[x] = find(p[x]);
    return p[x];
}

//以最左为根节点
void unite(int left, int right) {
    int rootx = find(left);
    int rooty = find(right);


    if (rootx != rooty) {
        nxt[points[rootx].r] = points[rooty].l;
        p[rooty] = rootx;
        points[rootx].r = points[rooty].r;
    }
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++) {
        p[i] = i;
        points[i].l = i;
        points[i].r = i;
        nxt[i] = 0;
    }
    for (int i = 1; i < n; i++) {
        cin >> x >> y;
        unite(x, y);
    }

    int head = points[find(n)].l;
    int isFirst = true;
    while (head != 0) {
        if (isFirst)isFirst = false;
        else {
            cout << " ";
        }
        cout << head;
        head = nxt[head];
    }
    return 0;
}