传送门 思路 这是一道hard题，但感觉并不是很hard。 题目要求一个无向图在保证其连通性下能删除的最大边数。那么用并查集的思想，可以理解为“给一个n个节点的图添加数量最少的无向边使其连通。” 为Alice和Bob两人各单独维护一个并查集，挨个加入每条边。如果当前边的两个顶点已经连通了，那么这个边就是一个多余边，直接计数器++。 值得注意的是，添加边的时候应该优先考虑type3的边，即公共边。因为公共边是共用的，考虑一种极端情况：对于同一个图，图中仅有type1、2边与仅有type3边。 因为对于每一个人，都要确保图的连通性，所以前者情况下，边数需要2*n=2n条，因为私有边不能公用；而后者情况下仅需要n条边，因为type3的边可以共用。以这个极端例子可以讨论在添加边的时候公有边优先级更高。 考虑非法状态，如果题目所给图对于二人中至少一人是非连通的，那么显然应该返回-1。 代码 ```cpp class Disjoint { private: unordered_map father; unordered_map rank; public: int cnt; void init(int n) { cnt = n; for (int i = 0; i < n; i++) { rank[i] = 1; father[i] = …
传送门 思路 力扣这个月的daily哟，已经变成了并查集的形状了。 题意很裸，本质上就是求联通分量的个数，和LeetCode每日一题：移除最多的同行或同列石头很像。两个连通分量相接通需要1条边，n个就需要n-1条边，求这个n并返回n-1作为答案就行了。 根据题设，显然有connections.size() < n-1时，返回-1. 代码 ```cpp class Solution { private: unordered_map father; unordered_map rank; public: int cnt; void init(int n) { cnt = n; for (int i = 0; i < n; i++) { rank[i] …
传送门 思路 题意挺简单的，就是在一个直角坐标系内给出若干点，求一个最小生成树，可以用prim直接写，也可以建图用 并查集维护边集再Kruskal。二者的介绍详见博客：最小生成树--Prim算法&Kruskal算法。 代码 prim ```cpp class Solution { public: int minCostConnectPoints(vector>& points) { const int n = points.size(); int ans = 0, mp[1005][1005], dis[1005]; bool flag[1005]={0}; memset(dis, 0x3f, sizeof(dis)); for (int i = 0; i < n; i++){ for (int j = …
传送门 题目大意 一个学校有n(n<=50000)个学生，他们都可能信仰不同的宗教，你不能一个一个去问他们的信仰，但你可以通过询问得知两个学生的信仰是否一致，询问有m(m<=n*(n-1)/2)次。通过询问你可以知道校内学生的信仰总数上限，找到这个上限作为答案。 思路 其实就是一个并查集，题目翻译过来就是说给你一个图与它的一些边，找到所有的联通分量。 代码 ```cpp #include #include #include #include #include using namespace std; const int N = 55000; int cnt; int n, m; int dad[N]; void init(int top) { for(int i = 1; i <= top; i++) { …
传送门 t1 千位分隔数 给定一个整型数，给它每三位加上一个分隔符。 做法有很多，憨一点可以用取出每一位数字来做，但看这个范围估计是要炸的，所以我这里选择转成string来做。 转成string，计数，每三位加上一个"."最后翻转一下就行了，记得处理一下前缀“.”。 ```cpp class Solution { public: string thousandSeparator(int n) { string str = to_string(n); if(n < 1000) return str; int m = str.size(); string ans = ""; int cnt = 0; for(int i = m-1; i >= 0; i--) { …
[图片缺失] 原图：https://www.edisoncgh.com/wp-content/uploads/2020/06/图-xmind-589x1024.png 图 逻辑结构 遍历 dfs 栈/递归 ①从图中某个顶点V0出发②找出刚访问的顶点的第一个邻接点，访问它并将他置位当前节点③重复步骤2直至当前节点不再有邻接点④返回上一个仍有邻接点并未被访问过的节点，重复步骤 bfs 队列 依次访问当前节点的每一个邻接点 存储结构 邻接矩阵 定义 设矩阵A，对于任意的Vi与Vj，若∈VR，则Aij＝1，反之为0 实现 有权图的邻接矩阵初值赋为∞，无权图初值为0. 再通过循环存入每一条弧。 复杂度 时间复杂度 存弧的时间复杂度为O(e)，赋初值的时间复杂度为O(n²) 空间复杂度 空间复杂度为O(n²) 特性 便于运算 因为使用矩阵存储，所以可以便捷地访问每一条弧。显然，判断弧存在、求顶点的度都可以在短时间内较优地完成 …