题解 | #Prim/Kruskal#

Prim

采用邻接矩阵，方便判重；

class Solution {
public:
    const int inf = 0x3f3f3f3f;
    struct Node{
        int v;
        int c;
        Node(int _v, int _c):v(_v), c(_c){}
        bool operator < (const Node& other) const{
            return c > other.c;
        }
    };
    int Adj[5010][5010];
    int vis[5010];
    int dist[5010];
    int miniSpanningTree(int n, int m, vector<vector<int> >& cost) {
        // write code here
        memset(Adj, inf, sizeof(Adj));
        memset(vis, false, sizeof(vis));
        memset(dist, inf, sizeof(dist));
        for(int i = 0 ; i < m; i ++){
            int u = cost[i][0] - 1;
            int v = cost[i][1] - 1;
            int c = cost[i][2];
            //去重边
            Adj[u][v] = min(Adj[u][v], c);
            Adj[v][u] = min(Adj[v][u], c);
        }
        priority_queue<Node> pq;
        pq.push({0, 0});
        dist[0] = 0;
        int ans = 0;
        int cnt = 0; //已经加入生成树集合的村庄数
        while(!pq.empty()){
            Node node = pq.top(); pq.pop();
            int u = node.v, cos = node.c;
            if(!vis[u]){
                ans += cos;
                vis[u] = true;
                cnt ++;
                if(cnt == n) break;
            }else continue;
            for(int v = 0; v < n; v ++){
                if(Adj[u][v] == inf) continue;
                int c = Adj[u][v];
                if(!vis[v] && c < dist[v]){
                    pq.push({v, c});
                    dist[v] = c;
                }
            }
        }
        return ans;
    }
};

Kruskal

class UnionSet{
private:
    vector<int> father;
public:
    UnionSet(int n){
        father.resize(n);
        for(int i = 0; i < n; i ++) father[i] = i;
    }
    int findFather(int x){
        if(father[x] != x) father[x] = findFather(father[x]);
        return father[x];
    }
    bool merge(int x, int y){
        int fa = findFather(x);
        int fb = findFather(y);
        if(fa != fb){
            father[fa] = fb;
            return true;
        }
        return false;
    }
};
class Solution {
public:
    struct Edge{
        int u, v;
        int cos;
        Edge(int _u, int _v, int _cos):u(_u), v(_v), cos(_cos){}
        bool operator < (const Edge& edge) const{
            return cos < edge.cos;
        }
    };
    int miniSpanningTree(int n, int m, vector<vector<int> >& cost) {
        // write code here
        UnionSet ust(n);
        unordered_map<int, unordered_map<int, int>> ump;
        for(int i = 0; i < m; i ++){
            int u = cost[i][0] - 1, v = cost[i][1] - 1, c = cost[i][2];
            if(u > v){
                swap(u, v);
            }
            if(ump.find(u) == ump.end() || ump[u].find(v) == ump[u].end()){
                ump[u][v] = c;
            }else{
                ump[u][v] = min(ump[u][v], c); //去重边
            }
        }
        vector<Edge> edges;
        for(auto it:ump){
            int u = it.first;
            auto mp = it.second;
            for(auto iit:mp){
                int v = iit.first, c = iit.second;
                edges.push_back({u, v, c});
            }
        }
        sort(edges.begin(), edges.end());
        m = edges.size();
        int ans = 0;
        for(int i = 0; i < m; i ++){
            int u = edges[i].u, v = edges[i].v, c = edges[i].cos;
            if(ust.merge(u, v)){
                ans += c;
            }
        }
        return ans;
    }
};