最小生成树—kruskal和prim算法
Kruskal算法模版 按各边权值进行从小到大排序 检测是否有环（使用并查集） 如果两节点属于同一个集合 则说明有环 如果两节点不属于同一个集合 不成环则进行合并 借助洛谷上的最小生成树 如题，给出一个无向图，求出最小生成树，如果该图不连通，则输出 orz。输入格式 第一行包含两个整数 N,MN,M，表示该图共有 NN 个结点和 MM 条无向边。 接下来 M...
并查集的原理和应用
1. 结构实现并查集要实现三个方法： int find(int x); 查找代表元素 bool isSameSet(int x, int y); 查看是否为同一集合 void _union(int x, int y); 合并集合 而并查集的结构，我们可以使用数组（顺序表）进行存储。数组下标i表示每个节点，数组的值father[i]对应着这个节点的代表节点。 ...
图的最短路径—BFS和Dijkstra算法
BFS使用场景针对无权图，给定一个起始点，要求其他点到起始点的最短路径，可以使用BFS（广度优先搜索）算法得出结果。 代码实现和原理分析给出下面一个图，假设起始点为3 使用distance数组和visited数组分别记录每个点的最短路径和该点是否被访问过。 如需记录最短路径，则需要path数组 123vector<int> distance(n+...
预算内的最多机器人数目——二分答案和单调队列
题目描述2398. 预算内的最多机器人数目 你有 n 个机器人，给你两个下标从 0 开始的整数数组 chargeTimes 和 runningCosts ，两者长度都为 n 。第 i 个机器人充电时间为 chargeTimes[i] 单位时间，花费 runningCosts[i] 单位时间运行。再给你一个整数 budget 。 运行 k 个机器人 总开销 是...