题解 | #最小生成树#
最小生成树
https://www.nowcoder.com/practice/735a34ff4672498b95660f43b7fcd628
class Solution { private: class UF //建立标准并查集,已进行路径压缩 { public: int count; vector<int> parents; UF(int n) { this -> count = n; parents.resize(n); for(int i = 0; i < n; ++i) parents[i] = i; } int find(int x) { if(parents[x] != x) parents[x] = find(parents[x]); return parents[x]; } bool connected(int x, int y) { int rootX = find(x); int rootY = find(y); return rootX == rootY; } void Union(int x, int y) { int rootX = find(x); int rootY = find(y); if(rootX != rootY) { parents[rootX] = rootY; --count; } } int _count() { return count; } }; public: int miniSpanningTree(int n, int m, vector<vector<int> >& cost) { UF uf(n + 1); //题目从1到n编号因此要使用n + 1作为参数 int mst = 0; sort(cost.begin(), cost.end(), [](vector<int> a, vector<int> b){return a[2] < b[2];}); //贪心算法,将短边排在前面。 for(vector<int> cos : cost) { int i = cos[0]; int j = cos[1]; if(!uf.connected(i, j)) //判断i,j是否已联通,若已经联通则不在需要Union { mst += cos[2]; uf.Union(i, j); } } return uf._count() == 2 ? mst : -1; //按正常情况此处应该等于1,但本题从1到n编号,其中0号为占位符,因此判断为等于2,其中为一个占位符加一棵树。 } };