题解 | 最小生成树

#include<iostream>
#include<vector>
#include<algorithm>
class USD
{
private:
public:
std::vector<int> rank;
std::vector<int> parent;
USD(int n)
{
    rank.resize(n+1,0);
    parent.resize(n+1,0);
    for(int i=0;i<parent.size(); i++)
    {
        parent[i]=i;
    }
}

int Find(int node)
{
    return node==parent[node]? node:parent[node]=Find(parent[node]);//先递归调用再返回
}

bool Union(int a,int b)
{
    int ra=Find(a);
    int rb=Find(b);
    if(ra==rb) return false;
    if(rank[ra]<rank[rb]) parent[ra]=rb;
    if(rank[ra]>=rank[rb]) 
    {
        parent[rb]=ra;
        if(rank[ra]==rank[rb]) rank[ra]++;
    }
    return true;
}


};

bool compare(std::vector<int>& a, std::vector<int>& b)
{
    return a[2]<b[2];
}

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回最小的花费代价使得这n户人家连接起来
     * @param n int整型 n户人家的村庄
     * @param m int整型 m条路
     * @param cost int整型vector<vector<>> 一维3个参数，表示连接1个村庄到另外1个村庄的花费的代价
     * @return int整型
     */
    int miniSpanningTree(int n, int m, vector<vector<int> >& cost) {
        // write code here
        std::sort(cost.begin(),cost.end(),compare);
        int money=0;
        int EdgeUsed=0;
        USD usd(n);
        for(int j=0;j<cost.size();j++)
        {
            int u,v,w;
            
            u=cost[j][0];
            v=cost[j][1];
            w=cost[j][2];
            if(usd.Union(u,v))
            {
                money+=w;
                EdgeUsed++;
                if(EdgeUsed==n-1) break;
            }

        }
        return EdgeUsed == n - 1 ? money : -1; // 若不能连通所有村庄，返回 -1
    }
};

这道题典型的最小生成树的例题，作为复习。

其中最主要的并查集（disjoint set union）实现三个功能：节点初始化，查找父节点，加入生成树。其中查找父节点的三元写法注意是先递归结果返回给parent[node]之后再return（表达式的右值即为表达式的值）；加入生成树这个功能（Union）注意Find函数已经为a,b节点找到了溯源路径，则最优安排方案应该与比较ra与rb的秩来决定如何加入生成树。

另外，Kruskal的终止条件一定要记住是生成树已有n-1条边

最后关于sort， 要注意compare的运用；或者可以利用lamda的性质去写，

 sort(cost.begin(), cost.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[2] < b[2];
        });


/*[捕获列表] (参数列表) -> 返回类型 {
    函数体
}*/

墓前就这样吧，希望之后笔试面试还记得怎么写，多多重复百炼成钢