本文共 2054 字,大约阅读时间需要 6 分钟。
并查集(Union-Find)是一种高效的数据结构,广泛应用于处理动态的连通性问题。以下是优化过的技术文档,基于用户的要求已进行适当修改,确保内容具有专业性和可读性。
我们需要处理多组朋友关系,并找到每组的根节点数目。同一个集合的所有节点应共享一个根节点,最终统计这些根节点的数量即可。
在查找根节点时,将当前节点的父节点指向其祖父。这样做可以减少查找时间,因为每次查找时路径会被缩短。
int findFather(int x) { if (father[x] != x) { father[x] = findFather(father[x]); } return father[x];}
void Union(int a, int b) { int fa = findFather(a); int fb = findFather(b); if (fa != fb) { father[fa] = fb; }}
void init(int n) { for (int i = 1; i <= n; ++i) { father[i] = i; }}
#include#include #include #include #include using namespace std;const int maxn = 101;int father[maxn];int isRoot[maxn]; // 是否为根节点标记int findFather(int x) { if (father[x] != x) { father[x] = findFather(father[x]); } return father[x];}void Union(int a, int b) { int fa = findFather(a); int fb = findFather(b); if (fa != fb) { father[fa] = fb; }}void init(int n) { for (int i = 1; i <= n; ++i) { father[i] = i; isRoot[i] = false; }}int main() { cin >> n >> m; init(n); for (int i = 0; i < m; ++i) { int a, b; cin >> a >> b; Union(a, b); } for (int i = 1; i <= n; ++i) { isRoot[findFather(i)] = true; } int ans = 0; for (int i = 1; i <= n; ++i) { if (isRoot[i]) { ans++; } } cout << ans << endl; return 0;}
通过这段优化代码,可以高效地解决类似问题,找到每个集合的根节点数目。该方案适用于动态数据的连通性问题,是数据结构和算法学习中的基础内容。
转载地址:http://ndapz.baihongyu.com/