FJUT寒假作业第三周数蚂蚁(记录第一道并查集)
2024-10-14 08:50:32
http://210.34.193.66:8080/vj/Contest.jsp?cid=162#P7
思路：用并查集合并集合，最后遍历，找到集合的根的个数。
并查集是森林，森林中的每一颗树是一个集合。我们用一个数组，数组的下标是元素的值。数组存放着其父节点的位置。这样我们就能用数组画出多颗树。
也就是并查集。
初始化并查集，n含义如题。
在并查集中查找数值为x的根节点。根节点的父节点就是本身，当不是跟节点是，继续找。
并查集路径压缩（优化）。在获得了跟节点后，把查找过程中遇到的节点比属于同一集合，让他们的父节点之间改为跟，提高之后查找的效率
另外附上另一种递归，一行写完的找根+路径压缩
集合合并，把x,y所在的集合合并，将其中一个集合的根节点连在另一个根节点上。
最后遍历获得答案ans
最新文章
- 在其它路径新建cocos2d-x项目
- cloudstack的ZONE删除不掉？来这招吧
- windows bat命令编写大全
- ViewData ViewBag ViewModel
- 基于 HTML5 WebGL 的 3D 仪表数据监控
- 《高级软件测试》JIRA使用手册（二）JIRA安装
- [Swift]LeetCode609. 在系统中查找重复文件 | Find Duplicate File in System
- Groovy 设计模式 -- 享元模式
- TypeScript安装备忘：npm proxy设置
- 2522 和为K的倍数
- C#编程の泛型编程
- JSP(4)—Cookie创建及简单案例(自动登录)
- 解决IIS8中 URLRewriter 不能使用的方法
- Oracle数据库select语句
- ML: 聚类算法R包-层次聚类
- unity3D iTween的使用
- Windows server 2012 R2 与 Windows 2016 的双系统重启选项
- Android开发之模仿UC浏览器的菜单
- 第二百六十九节，Tornado框架-Session登录判断
- 第1天：jQuery效果