【模板】最小生成树

题目来自洛谷网站：

思路：

kruskal模板题。

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5+20;int n, m;
//要根据w排序决定最小还是最大树
struct edge{int u, v, w;bool operator<(const edge &t) const {return w < t.w ;}
}e[N];
int fa[N];//并查集 存树中该点的父节点
//存最后答案
int ans;
//判断无向图能不能生成最小树
int cnt;int find(int x){if(fa[x] == x) return x;return fa[x]=find(fa[x]);
}bool kruskal(){//先排序 题目要求最小生成树sort(e, e+m);for(int i = 0; i < m; i++){int x = e[i].u, y = e[i].v;int a = find(x), b = find(y);if(a == b) continue;fa[a] = b;ans += e[i].w;cnt ++;}return cnt == n-1;
}signed main(){cin >> n >> m;//初始化for(int i = 0; i<=n; i++) fa[i] = i;//数据读入到tree中for(int i = 0; i<m; i++){cin >> e[i].u >> e[i].v >> e[i].w;}bool check = kruskal();if(check) cout << ans << endl;else cout << "orz" << endl;return 0;
}