并查集及其优化

并查集

并查集是一种树型数据结构，用于处理一些动态集合的合并及查询问题。

并查集的基本操作有：

合并：将两个集合合并为一个集合。
查询：判断两个元素是否属于同一个集合。

并查集的应用场景有：

动态连通性：判断两个点是否连通。
最小生成树：计算最小生成树。
路径压缩：减少树的高度。

并查集优化

并查集有两种启发式优化。第一种是路径压缩，即将每个节点的父节点压缩到根节点，总时间复杂度为 \(O(n\alpha)\)，其中 \(\alpha\) 为一常数。但是会破坏树形结构。

另一种是按秩合并，即将两个集合合并时，选择秩较大的集合作为根节点，总时间复杂度为 \(O(n\log n)\)。由于并其没有破坏树形结构，所以可以实现一些撤回操作。

路径压缩

路径压缩的基本思想是将每个节点的父节点压缩到根节点，这样可以减少树的高度，使得查询操作更快。

// 初始化 parent[i] = i
int find(int x) {
    return x == parent[x]? x : parent[x] = find(parent[x]);
}

按秩合并

我们从一道例题开始。

UVA11354

大意：求最小生成树的两个点间的最大路径。

带边权的并查集？多组数据？我们按秩合并。基本思想是使深度较小结点的树的根指向包含较多结点的树的根。

我们存边时，用结构体存边。但不用前向星。因为如果要 Kruskal 的话需要改动一下。本来我们连接最短的边时，如果两端的端点的父亲不一样的话直接连上就可以了。但是按秩排序不一样。他既要优化又要不破坏树形结构，我们就造一个秩rank，rank[i]表示的相当于子树大小或者深度的东西，每次查询就把小的连到大的上并直接把边权直接连到父亲结点上，那么就能保留原来的树形结构并做到优化。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <ctype.h>
#include <cstring>
using namespace std;
const int maxn = 50010;
inline int read()
{
    int x = 0, w = 1;
    char c = getchar();
    while (!isdigit(c))
    {
        if (c == '-')
            w = -1;
        c = getchar();
    }
    while (isdigit(c))
        x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
    return x * w;
}
int n, m, t;
int fa[maxn], e[maxn], rank[maxn];
struct data
{ // 这是边
    int x, y, z;
} a[maxn];

inline bool cmp(data a, data b) { return a.z < b.z; }
inline int find(int x) { return fa[x] == x ? x : find(fa[x]); }
inline void kruskal()
{
    int s = 0, f1, f2;
    for (int i = 1; i <= n; i++)
        fa[i] = i, rank[i] = 1;
    for (int i = 1; i <= m; i++)
    {
        f1 = find(a[i].x);
        f2 = find(a[i].y);
        if (f1 != f2)
        {
            if (rank[f1] < rank[f2])
            {
                fa[f1] = f2;
                e[f1] = a[i].z;
                rank[f2] = max(rank[f2], rank[f1] + 1);
            } // 高度大的做小的的根
            else
            {
                fa[f2] = f1;
                e[f2] = a[i].z;
                rank[f1] = max(rank[f1], rank[f2] + 1);
            } // 相等或者相反就相反来
            s++;
        }
        if (s == n - 1)
            break;
    }
}
int c[maxn];
int query(int x, int y)
{
    for (int i = 1; i <= n; i++)
        c[i] = -1;
    int tmp = 0, ans = 0;
    while (1)
    {
        c[x] = tmp; // c是从x开始向上边的最大值。
        if (fa[x] == x)
            break;
        tmp = max(tmp, e[x]); // e代表向上连接的边权
        x = fa[x];            // 向上爬
    }
    while (1)
    {
        if (c[y] >= 0)
        {
            ans = max(ans, c[y]);
            break;
        } // 找到LCA就break
        if (fa[y] == y)
            break; // 或者找到根
        ans = max(ans, e[y]);
        y = fa[y];
    } // 因为一定会集中到LCA就直接用ans
    return ans;
}
int main()
{
    while (~scanf("%d%d", &n, &m))
    {
        for (int i = 1; i <= m; i++)
        {
            a[i] = (data){read(), read(), read()};
        }
        sort(a + 1, a + 1 + m, cmp);
        kruskal();
        t = read();
        for (int x, y, i = 1; i <= t; i++)
        {
            x = read(), y = read();
            printf("%d\n", query(x, y));
        }
    }
    return 0;
}

按秩合并不仅仅能够处理最小生成树问题，也可以处理一些大规模数据的动态加边和查询问题，每次连边后可以记录两个秩的大小，非常的方便。