C++U7-09-并查集

并查集（Disjoint Set Union）是一种树型的数据结构，主要用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。

并查集能解决什么问题？

1. 在线游戏公会管理：
   • 应用场景：在一个大型多人在线游戏中，玩家可以创建或加入公会（公会相当于一个团队或群体）。随着时间的推移，公会可能会合并或解散。
   • 并查集应用：可以使用并查集来跟踪和管理公会之间的关系。当两个公会合并时，使用并查集的合并操作将它们合并为一个公会。当需要查询某个玩家所在的公会时，可以使用并查集的查找操作快速找到。
2. 电商网站的推荐系统：
   • 应用场景：电商网站希望根据用户的购买历史和浏览行为，为用户推荐相似的商品或感兴趣的店铺。
   • 并查集应用：可以将具有相似购买习惯或兴趣的用户视为一个“兴趣组”。当新用户加入时，可以根据其历史行为将其添加到相应的兴趣组中。使用并查集可以方便地合并和查找这些兴趣组，从而更准确地为用户推荐商品或店铺。
3. 地理区域划分：
   • 应用场景：在一个大型城市规划项目中，需要将城市划分为不同的区域，每个区域具有相似的地理特征或功能。
   • 并查集应用：可以将每个地理区域视为一个集合，并使用并查集来管理这些集合。当两个区域具有相似的特征或需要合并时，使用并查集的合并操作将它们合并为一个区域。当需要查询某个地点的所属区域时，可以使用并查集的查找操作快速找到。

并查集数据结构主要用于解决与集合合并和查询相关的一系列算法问题。以下是并查集能够解决的主要算法问题，以及参考文章中的相关信息：

1. 集合合并与查询：
   • 并查集的基本功能包括将两个集合合并以及查询两个元素是否属于同一个集合。这两个操作的时间复杂度近乎O(1)，使其在处理大量数据时非常高效。
   • 在具体实现中，并查集通过数组来实现，数组的索引代表一个节点所存储的元素，索引的值代表节点所在的组标识符（即组号）。
2. 社交网络中的好友圈关系建立与查询：
   • 在社交网络中，人们之间存在好友关系。通过并查集，可以方便地建立和查询好友圈关系。将每个人看作一个节点，当两个人成为好友时，将它们所在的两个集合进行合并操作。通过查询某两个人是否属于同一个集合，可以判断他们是否在同一个好友圈中。
3. 电子地图中的连接性问题解决：
   • 在电子地图中，经常需要判断两个地点之间是否存在路径。并查集可以用来解决这个连接性问题。将地图上的每个地点看作一个节点，当两个地点之间存在路径时，将它们所在的两个集合进行合并操作。通过查询两个地点是否属于同一个集合，可以判断它们之间是否存在路径。
4. 优化方式：
   • 并查集在实现过程中可以采用一些优化方式来提高效率，如路径压缩和按秩合并。这些优化方式能够进一步减少查询和合并操作的时间复杂度。

综上所述，并查集数据结构主要用于解决与集合合并和查询相关的算法问题，特别适用于社交网络分析、电子地图路径查询等场景。通过高效的查询和合并操作，并查集能够快速地处理大量数据，为实际应用提供有力的支持。

 路径优化

[【并查集】并查集]

【算法分析】
并查集的模板题目，注意当两个元素不在同一集合中再进行合并。

【参考代码】
#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e4 + 9;
int fa[maxn];
int get(int x) {
    if (fa[x] == x) return x;
    return fa[x] = get(fa[x]);
}
void merge(int x, int y) {
    fa[get(x)] = get(y);
}
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) fa[i] = i;
    while (m--) {
        int z, x, y;
        cin >> z >> x >> y;
        if (z == 1) {
            if (get(x) != get(y)) merge(x, y);
        }
        else {
            if (get(x) == get(y)) cout << "Y" << '\n';
            else cout << "N" << '\n';
        }
    }
    return 0;
}

[【并查集】朋友圈的数量]

【算法分析】
每个朋友圈可以认为是一个集合，则就是求有几个不同的集合，可以使用并查集，并查集中每个集合都有一个代表元素，其实就是求代表元素的个数。

【参考代码】
#include<bits/stdc++.h>
using namespace std;

const int maxn = 2e5 + 9;
int fa[maxn];
int get(int x) {
    if (fa[x] == x) return x;
    return fa[x] = get(fa[x]);
}
void merge(int x, int y) {
    fa[get(x)] = get(y);
}
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) fa[i] = i;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        if (get(u) != get(v)) merge(u, v);
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        if (fa[i] == i) ans++;
    }
    cout << ans << '\n';
    return 0;
}

按秩合并：

在并查集（Union-Find）的数据结构中，秩（Rank）是一个用于优化合并操作（Union）的概念。秩通常有两种常见的定义方式：

1. 树的深度（Height）：在这种定义下，秩表示以某个元素为根的树的深度。每次执行find操作进行路径压缩时，树的深度可能会改变，但我们可以使用额外的信息（如父节点数组和额外的标记数组）来追踪和更新每个集合的秩（或深度）。这种实现中，合并两个集合时，将深度较小的树连接到深度较大的树上，以保持树的平衡。

2. 集合的大小（Size）：在这种定义下，秩表示以某个元素为根的集合中元素的数量。合并两个集合时，将元素数量较少的集合合并到元素数量较多的集合中。与基于深度的秩相比，基于大小的秩更直观，并且通常在实际应用中性能也相近或更优。

使用秩优化的目的是在多次合并操作后，保持并查集中树的平均高度尽可能低，从而减少find操作的平均时间复杂度。在只使用普通合并操作的并查集中，最坏情况下find操作的时间复杂度可能达到O(n)，其中n是集合中元素的数量。但是，通过使用秩（无论是基于深度还是基于大小）进行优化，find操作的平均时间复杂度可以降低到O(α(n))，其中α是Ackermann函数的反函数，对于实际应用来说，其增长非常缓慢，可以视为常数时间复杂度。

因此，在并查集的实现中，秩是一个非常重要的概念，用于优化合并操作，提高并查集的性能。

作业分析讲解：

链接：https://pan.baidu.com/s/1ltDCx2fI6IhsP2iUjeJLxg?pwd=0000
提取码：0000