传送门 思路 这是一道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 = …
传送门 思路 可以把所有在同一行和同一列的石子连起来，这样就能构成若干个连通分量。而根据题意，不难想到每一个连通分量最后都能删到只剩一颗石子，所以答案显然就是石子总数减去连通分量的个数。 用并查集来维护连通关系。 代码 第一种是最直接的O(n²)连图。 ```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++) { father[i] = i; rank[i] = 1; } } int …
传送门 题目大意 一个学校有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++) { …