NC159. 最小生成树
描述
示例1
输入:
3,3,[[1,3,3],[1,2,1],[2,3,1]]
输出:
2
示例2
输入:
2,1,[[1,2,1]]
输出:
1
C++ 解法, 执行用时: 3ms, 内存消耗: 376KB, 提交时间: 2021-07-13
class Solution {
public:
struct Element {
int value;
Element *next;
Element() : next(this) {}
Element(int v) : value(v), next(this) {}
};
struct UnionFindSet {
vector<Element *> pElement_vec;
unordered_map<Element *, int> pElement_i_unmap;
UnionFindSet(int n){
int i = 0;
while(i < n)
{
Element *pElement = new Element(i);
pElement_vec.push_back(pElement);
pElement_i_unmap[pElement] = 1;
i++;
}
}
~UnionFindSet(){
for(auto pElement : pElement_vec)
delete pElement;
}
Element *find_Head(Element *pElement){
if(pElement->next == pElement) return pElement;
Element *p = pElement->next;
while(p != p->next) p = p->next;
while(pElement->next != p)
{
Element *p_tmp = pElement->next;
pElement->next = p;
pElement = p_tmp;
}
return p;
}
bool union_set(int lhs, int rhs)
{
Element *lhs_head = find_Head( pElement_vec[lhs] );
Element *rhs_head = find_Head( pElement_vec[rhs] );
if(lhs_head == rhs_head) return false;
Element *many_head =
pElement_i_unmap[lhs_head] >= pElement_i_unmap[rhs_head] ? lhs_head : rhs_head;
Element *few_head = many_head == lhs_head ? rhs_head : lhs_head;
pElement_i_unmap[many_head] += pElement_i_unmap[few_head];
pElement_i_unmap.erase( few_head ); few_head->next = many_head;
return true;
}
};
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* 返回最小的花费代价使得这n户人家连接起来
* @param n int n户人家的村庄
* @param m int m条路
* @param cost intvector<vector<>> 一维3个参数，表示连接1个村庄到另外1个村庄的花费的代价
* @return int
*/
int miniSpanningTree(int n, int m, vector<vector<int> >& cost) {
// write code here
UnionFindSet my_graph(n+1);
sort(cost.begin(), cost.end(),
[](const vector<int> &lhs, const vector<int> &rhs){
return lhs[2] < rhs[2];
});
int cnt = 0;
for(auto &i_vec : cost)
if( my_graph.union_set(i_vec[0], i_vec[1]) )
cnt += i_vec[2];
return cnt;
}
};
C++ 解法, 执行用时: 3ms, 内存消耗: 376KB, 提交时间: 2021-03-28
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* 返回最小的花费代价使得这n户人家连接起来
* @param n int n户人家的村庄
* @param m int m条路
* @param cost intvector<vector<>> 一维3个参数，表示连接1个村庄到另外1个村庄的花费的代价
* @return int
*/
struct Edge{
int from;
int to;
int length;
bool operator<(const Edge& x){
return length<x.length;
}
};
Edge edge[10010];
int height[10010];
int father[10010];
void Initial(int n){
for(int i=1;i<=n;i++){
height[i]=0;
father[i]=i;
}
}
int find(int x){
if(x!=father[x]) x= find(father[x]);
return x;
}
void Union(int x,int y){
x=find(x);
y=find(y);
if(height[x]>height[y]) father[y]=x;
else if(height[y]>height[x]) father[x]=y;
else {
father[y]=x;
height[x]++;
}
}
int floyd(int m){
int sum=0;
sort(edge, edge+m);
for(int i=0;i<m;i++){
if(find(edge[i].from)!=find(edge[i].to)){
Union(edge[i].from, edge[i].to);
sum+=edge[i].length;
}
}
return sum;
}
int miniSpanningTree(int n, int m, vector<vector<int> >& cost) {
for(int i=0;i<m;i++){
edge[i].from=cost[i][0];
edge[i].to=cost[i][1];
edge[i].length=cost[i][2];
}
Initial(n);
return floyd(m);
}
};
C++ 解法, 执行用时: 3ms, 内存消耗: 376KB, 提交时间: 2021-03-22
class Solution {
public:
static bool cmp(vector<int>&x ,vector<int> &y) {
return x[2]<y[2];
}
int find(vector<int> &p,int x) {
if(p[x] !=x) p[x] = find(p,p[x]);
return p[x];
}
int miniSpanningTree(int n, int m, vector<vector<int> >& cost) {
// write code here
vector<int> parent(n+1);
for(int i=0;i<=n;++i) parent[i] = i;
sort(cost.begin(),cost.end(),cmp);
int res=0;
for(vector<int>&v: cost) {
int x = v[0],y=v[1],w = v[2];
int px = find(parent,x),py = find(parent,y);
if(px!=py) {
res+=w;
parent[px] = py;
}
}
return res;
}
};
C++ 解法, 执行用时: 3ms, 内存消耗: 376KB, 提交时间: 2021-03-16
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* 返回最小的花费代价使得这n户人家连接起来
* @param n int n户人家的村庄
* @param m int m条路
* @param cost intvector<vector<>> 一维3个参数，表示连接1个村庄到另外1个村庄的花费的代价
* @return int
*/
class UnionFind{
private:
vector<int> v;
public:
UnionFind(int n):v(n, -1){}
int Find(int i){
return (v[i]==-1)?i:(Find(v[i]));
}
void Union(int i, int j){
int x = Find(i);
int y = Find(j);
if (x!=y){
v[x] = y;
}
}
bool sameset(int i, int j){
return (Find(i) == Find(j));
}
};
int miniSpanningTree(int n, int m, vector<vector<int> >& cost) {
// write code here
sort(cost.begin(), cost.end(),
[](const vector<int>& a, const vector<int>& b)->bool{
return a[2] < b[2];
});
UnionFind u(n+1);
int rtn = 0;
int tmp = 0;
for (vector<int>& v : cost){
int a = u.Find(v[0]);
int b = u.Find(v[1]);
if (a != b){
u.Union(a, b);
rtn += v[2];
tmp ++;
if (tmp == n-1){
break;
}
}
}
return rtn;
}
};
C++ 解法, 执行用时: 3ms, 内存消耗: 380KB, 提交时间: 2021-03-07
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* 返回最小的花费代价使得这n户人家连接起来
* @param n int n户人家的村庄
* @param m int m条路
* @param cost intvector<vector<>> 一维3个参数，表示连接1个村庄到另外1个村庄的花费的代价
* @return int
*/
struct edge{
int start;
int end;
int cost;
edge(int s=0,int e=0,int c=0):start(s),end(e),cost(c){
}
};
vector<int>parent;
int find(int val){
if(parent[val]==-1)
return val;
else
return find(parent[val]);
}
int miniSpanningTree(int n, int m, vector<vector<int> >& cost) {
// write code here
vector<edge>edges;
parent.resize(n+1,-1);
for(int i=0;i<m;i++){
edges.push_back(edge(cost[i][0],cost[i][1],cost[i][2]));
}
sort(edges.begin(),edges.end(),[](edge&left,edge&right){return left.cost<right.cost;});
int res=0;
int count=0;
for(int i=0;i<m;i++){
auto cur=edges[i];
int x=find(cur.start);
int y=find(cur.end);
if(x!=y){
++count;
res+=cur.cost;
parent[x]=y;
if(count==n-1)
break;
}
}
return res;
}
};