并查集

并查集

1、并查集是一种支持合并和查询操作的集合形式的数据结构，它支持两个集合的合并，并可以查询点与点之间的连通关系
2、并查集只需要一个数组 $pre[]$ 存储点的前导点(父节点)，在初始化时 $pre[i] = i$ ，表示点与自己连通，是单独的连通块，该功能由 $init()$ 函数完成。并查集中还需要一个函数 $root(u)$ ，该操作将找到点 $u$ 所属的连通块(的根节点)。该函数将递归查找 $u$ 的父节点，直至找到根节点
3、对于两个点 $u$ 和 $v$ 的合并操作，只需要将 $u$ 和 $v$ 所属的连通块的其中一个根指向另一个根即可，如 $pre[root(u)] = root(v)$ ；对于两个点 $u$ 和 $v$ 的查询操作，只需要判断 $u$ 和 $v$ 所属的连通块的根是否相同即可
4、但前述 $root(u)$ 函数的朴素算法每次都需要查找一整条父节点，效率太低，可以通过路径压缩优化程序： $pre[u] = (pre[u] == u ? u : root(pre[u]))$ ，这样同一连通块在第一次查找后，每个节点都将直接指向当前根节点，提高以后查找的效率
```
const int N = 1e5 + 10;
int pre[N];

// 初始化函数
void init(int n)
{
    for (int i = 0; i <= n; i++)
        pre[i] = i;
}

// 朴素算法的 root()
int root_(int u)
{
    if (pre[u] == u)
        return u;
    return pre[u];
}

// 路径压缩的 root()
int root(int u)
{
    return pre[u] = (pre[u] == u ? u : root(pre[u]));
}

// 合并操作
void merge(int u, int v)
{
    pre[root(u)] = root(v);
}

// 查找操作
bool isCon(int u, int v)
{
    return root(u) == root(v);
}
```

例-连通块问题

连通块问题

1、连通块问题：给定一个无向图，包含 $m$ 个点 $n$ 条边(没有重边和自环)，求图中所有连通块大小，升序输出。如示例中有 $5$ 个点 $2$ 条边，两条边为$\{1, 2\}, \{1, 3\}$，则构成了三个连通块 $\{1, 2, 3\}, \{4\}, \{5\}$，所以升序输出大小 $1 1 3$
2、通过并查集，合并和区分连通块十分容易，如何知道连通块的大小？可以根据桶的思想，用桶统计连通块的大小，再从桶中找出有效答案，排序输出

代码实现

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10;
int pre[N], ct[N]; // ct 作为桶，统计连通块的大小

void init(int n)
{
    for (int i = 0; i <= n; i++)
        pre[i] = i;
}

int root(int u)
{
    return pre[u] = (pre[u] == u ? u : root(pre[u]));
}

void merge(int u, int v)
{
    pre[root(u)] = root(v);
}

bool isCon(int u, int v)
{
    return root(u) == root(v);
}

void solve()
{
    int n, m;
    cin >> n >> m;

    init(n);
    for (int i = 1; i <= m; i++)
    {
        int u, v;
        cin >> u >> v;
        merge(u, v);
    }

    // 用桶统计连通块的大小
    for (int i = 1; i <= n; i++)
        ++ct[root(i)];

    vector<int> ans; // 用 ans 记录答案
    for (int i = 1; i <= n; i++)
        if (ct[i]) // 如果根节点为 i 的连通块大小不为 0
            ans.push_back(ct[i]);

    // 排序并输出答案
    sort(ans.begin(), ans.end());
    for (int &it : ans)
        cout << it << ' ';
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T = 1;
    // cin >> T;
    while (T--)
        solve();
    return 0;
}

并查集

例-连通块问题

页底评论