每日一題 No.54 最小生成樹問題（Kruskal算法）

本題要求：

給出一個有向圖，讓你求出這個圖的最小生成樹

輸入格式：

第一行輸入V，E分别代表頂點數和邊數

接下來E行，每行輸入from to cost 代表從from到to的距離為cost

輸出格式：

輸出最小消耗

輸入樣例：

3 3

0 1 2

1 2 3

0 2 4

輸出樣例：

5

解題思路 :

按照邊的權值的順序從大到小檢視一遍。

代碼 :

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;  

class Edge {
    public:
        int u;
        int v;
        int cost;
        Edge(int u, int v, int cost) {
            this->u = u;
            this->v = v;
            this->cost = cost;
        }
        Edge() {
        }
};
using namespace std;  

int par[];
int rank[];

void init(int n) {
    for (int i = ; i < n; i++) {
        par[i] = i;
        rank[i] = ;
    }
}

int find(int x) {
    if (par[x] == x) {
        return x;
    } else {
        return par[x] = find(par[x]);
    }
}

void unite(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) {
        return;
    } else if (rank[x] < rank[y]){
        par[x] = y;
    } else {
        par[y] = x;
        if (rank[x] == rank[y]) {
            rank[x]++;
        }
    }
}

bool same(int x, int y) {
    return find(x) == find(y); 
} 

bool comp(const Edge& e1, const Edge& e2) {
    return e1.cost < e2.cost;
}
vector<Edge> es;
int V, E;

int kruskal() {
    sort(es.begin(), es.end(), comp);
    init(V);
    int res = ;
    for (int i = ; i < E; i++) {
        Edge e = es[i];
        if (!same(e.u, e.v)) {
            unite(e.u, e.v);
            res += e.cost;
        }
    }
    return res;
}
int main() {
    bool used[];
    cin >> V >> E;
    for (int i = ; i < E; i++) {
        int f, t, c;
        cin >> f >> t >> c;
        es.push_back(Edge(f, t ,c));
    }
    cout << kruskal();
    return ; 
}