思路讲解
261. 以图判树(中等)
题目:
给定编号从 0 到 n - 1 的 n 个结点。给定一个整数 n 和一个 edges 列表,其中 edges[i] = [ai, bi] 表示图中节点 ai 和 bi 之间存在一条无向边。
如果这些边能够形成一个合法有效的树结构,则返回 true ,否则返回 false 。
示例 1:
输入: n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]
输出: true
示例 2:
输入: n = 5, edges = [[0,1],[1,2],[2,3],[1,3],[1,4]]
输出: false
因为包含了环
思路:
使用并查集,当一条边的两个节点已经处于联通状态时,新加的边就肯定构成了环。
对于添加的这条边,如果该边的两个节点本来就在同一连通分量里,那么添加这条边会产生环;反之,如果该边的两个节点不在同一连通分量里,则添加这条边不会产生环。
class Solution { public: bool validTree(int n, vector<vector<int>>& edges) { UF uf(n); // 遍历所有边,将组成边的两个节点进行连接 for(int i=0;i<edges.size();++i){ int p=edges[i][0]; int q=edges[i][1]; // 若两个节点已经在同一连通分量中,会产生环 if(uf.connected(p,q)){ return false; } // 这条边不会产生环,可以是树的一部分 uf.Union(p,q); } // 要保证最后只形成了一棵树,即只有一个连通分量 return uf.count==1; } class UF{ public: UF(int n){ count=n; for(int i=0;i<n;++i){ parent.push_back(i); size.push_back(1); } } void Union(int p,int q){ int rootp=find(p); int rootq=find(q); if(rootp==rootq){ return; } if(size[rootp]>size[rootq]){ size[rootq]+=size[rootp]; parent[rootp]=rootq; }else{ size[rootq]+=size[rootp]; parent[rootq]=rootp; } count--; } int find(int x){ while(x!=parent[x]){ parent[x]=parent[parent[x]]; x=parent[x]; } return x; } bool connected(int p,int q){ int rootp=find(p); int rootq=find(q); return rootp==rootq; } int count; vector<int> parent; vector<int> size; }; };
1135. 最低成本联通所有城市(中等)
题目:
思路:
1、包含图中的所有节点。
2、形成的结构是树结构(即不存在环)。
3、权重和最小。
前两点用并查集来判断,第三点使用贪心:
将所有边按照权重从小到大排序,从权重最小的边开始遍历,如果这条边和mst
中的其它边不会形成环,则这条边是最小生成树的一部分,将它加入mst
集合;否则,这条边不是最小生成树的一部分,不要把它加入mst
集合。
class Solution { public: int minimumCost(int n, vector<vector<int>>& connections) { // 城市编号为 1...n,所以初始化大小为 n + 1 UF uf(n+1); // 对所有边按照权重从小到大排序 sort(connections.begin(),connections.end(), [](const vector<int>& a, const vector<int>& b){ return a[2]<b[2]; }); // 记录最小生成树的权重之和 int sum=0; for(int i=0;i<connections.size();++i){ int p=connections[i][0]; int q=connections[i][1]; int cost=connections[i][2]; // 若这条边会产生环,则不能加入 mst if(uf.connected(p,q)){ continue; } // 若这条边不会产生环,则属于最小生成树 sum+=cost; uf.Union(p,q); } // 保证所有节点都被连通 // 按理说 uf.count() == 1 说明所有节点被连通 // 但因为节点 0 没有被使用,所以 0 会额外占用一个连通分量 return uf.count==2?sum:-1; } class UF{ public: UF(int n){ count=n; for(int i=0;i<n;++i){ parent.push_back(i); size.push_back(1); } } void Union(int p,int q){ int rootp=find(p); int rootq=find(q); if(rootp==rootq) return; parent[rootp]=rootq; count--; } int find(int x){ while(x!=parent[x]){ parent[x]=parent[parent[x]]; x=parent[x]; } return x; } bool connected(int p, int q){ int rootp=find(p); int rootq=find(q); return rootp==rootq; } int count; vector<int> parent; vector<int> size; }; };
1584. 连接所有点的最小费用(中等)
题目:
思路:
很显然这也是一个标准的最小生成树问题:每个点就是无向加权图中的节点,边的权重就是曼哈顿距离,连接所有点的最小费用就是最小生成树的权重和。
所以解法思路就是先生成所有的边以及权重,然后对这些边执行 Kruskal 算法即可:
class Solution { public: int minCostConnectPoints(vector<vector<int>>& points) { vector<vector<int>> graph; int n=points.size(); // 生成所有边及权重 for(int i=0;i<n;++i){ for(int j=i+1;j<n;++j){ int xi=points[i][0]; int yi=points[i][1]; int xj=points[j][0]; int yj=points[j][1]; int cost=abs(xi-xj)+abs(yi-yj); // 用坐标点在 points 中的索引表示坐标点 graph.push_back({i,j,cost}); } } UF uf(n); // 将边按照权重从小到大排序 sort(graph.begin(),graph.end(), [](const vector<int>& a, const vector<int>& b){ return a[2]<b[2]; }); // 执行 Kruskal 算法 int sum=0; for(int i=0;i<graph.size();++i){ int p=graph[i][0]; int q=graph[i][1]; int cost=graph[i][2]; // 若这条边会产生环,则不能加入 mst if(uf.connected(p,q)){ continue; } // 若这条边不会产生环,则属于最小生成树 sum+=cost; uf.Union(p,q); } return sum; } class UF{ public: UF(int n){ count=n; for(int i=0;i<n;++i){ parent.push_back(i); size.push_back(1); } } void Union(int p, int q){ int rootp=find(p); int rootq=find(q); if(rootp==rootq) return; parent[rootp]=rootq; } int find(int x){ while(x!=parent[x]){ parent[x]=parent[parent[x]]; x=parent[x]; } return x; } bool connected(int p, int q){ int rootp=find(p); int rootq=find(q); return rootp==rootq; } int count; vector<int> parent; vector<int> size; }; };