积分商城

最新搜索： 88E1112 stm32f0 usb源码 TEF6686 adxl355 电池管理系统
您现在的位置是：首页 > 技术资料 > 用并查集求解朋友圈数量问题的过程
推荐星级：
  • 1
  • 2
  • 3
  • 4
  • 5

用并查集求解朋友圈数量问题的过程

更新时间：2026-10-17 12:14:21 大小：38K 上传用户：潇潇江南查看TA发布的资源 标签：Union-FindDisjoint SetConnected ComponentsPath CompressionGraph Algorithm 下载积分：2分 评价赚积分 （如何评价?） 打赏 收藏 评论(0) 举报

资料介绍

用并查集求解朋友圈数量问题的过程 问题定义 给定 个人以及他们之间的朋友关系（无向边），如果两个人直接或间接认识（通过朋友链），则他们属于同一个"朋友圈"。求一共有多少个互不相交的朋友圈。 例如 4 个人，关系为 0-1、1-2、3 孤立，则朋友圈数为 2。 问题分析 朋友圈数量问题本质上是"求无向图中连通分量的个数"。可以用并查集（Union-Find）高效解决：把有朋友关系的人合并到同一集合，最后统计不同的集合根节点数即可。 并查集的核心思想 并查集维护若干个不相交集合，支持两种操作： find(x)：找到 所在集合的代表元素（根）。 union(a, b)：合并 和 所在的两个集合。 通过路径压缩（find 时把路径上的节点直接指向根）和按秩合并（将小树并入大树），几乎可以在常数时间内完成操作。 C 代码实现 c#include

#define MAXN 1005int parent[MAXN], rank[MAXN];int find(int x) { if (parent[x] != x) parent[x] = find(parent[x]); // 路径压缩 return parent[x];}void unionSet(int a, int b) { int ra = find(a), rb = find(b); if (ra == rb) return; if (rank[ra] < rank[rb]) parent[ra] = rb; else if (rank[ra] > rank[rb]) parent[rb] = ra; else { parent[rb] = ra; rank[ra]++; }}int countCircles(int n, int friends[][2], int m) { for (int i = 0; i < n; i++) { parent[i] = i; rank[i] = 0; } for (int i = 0; i < m; i++) unionSet(friends[i][0], friends[i][1]); int count = 0; for (int i = 0; i < n; i++) if (find(i) == i) count++; // 根节点数即朋友圈数 return count;}int main() { int friends[][2] = {{0,1},{1,2}}; printf("朋友圈数 = %d\n", countCircles(4, friends, 2)); return 0;} 运行结果为 2，符合预期（0、1、2 一组，3 孤立）。 路径压缩的原理 find 时，把从 到根的路径上的所有节点直接连接到根节点上，这样后续的 find 操作就能跳过中间节点，几乎 完成。路径压缩是并查集高效的关键。 复杂度分析 时间复杂度： 次合并与 次查询，均摊复杂度近似 （反阿克曼函数，可视为常数）。 空间复杂度：parent 与 rank 数组，。 应用场景 并查集广泛应用于： 连通分量计数（本题）。 判断两个节点是否连通。 最小生成树中的环检测（配合 Kruskal）。 网络连通性分析。 朋友圈数量用并查集合并所有朋友关系，路径压缩后以近似常数时间求出连通分量个数。

部分文件列表

文件名 大小
用并查集求解朋友圈数量问题的过程.docx 38K

相关下载

全部评论(0)

暂无评论
评论赚积分>>

上传资源 上传优质资源有赏金

热门标签

更多>>

最新上传

  • 打赏
  • 30日榜单

热门下载

资料专题

推荐下载

本站上的所有资源均为源于网上收集或者由用户自行上传，仅供学习和研究使用，无任何商业目的，版权归原作如有侵权，请 来信指出，本站将立即改正。

ICP许可证号：京ICP证070360号     21IC电子网 2000- 版权所有

京ICP备11013301号

京公网安备 11010802024343号