@[zhuyuhao1123](/user/526470) 使用并查集即可
by aeiouaoeiu @ 2024-10-09 22:28:01
记录总共经过了多少个点
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 5e3 + 6, M = 2e5 + 6;
int n, m, ds[N], ans, num;
struct edge{int x, y, z;}e[M<<1];
int find(int x){return ds[x] < 0 ? x : ds[x] = find(ds[x]);}
bool mst(){
for(int i = 1; i <= m<<1; ++ i){
if(num == n-1) break;
int x = find(e[i].x), y = find(e[i].y);
if(x == y) continue;
ds[x] = y, ans += e[i].z, num ++;
}
if(num == n-1) return 1;
return 0;
}
int main(){
memset(ds, -1, sizeof ds);
scanf("%d%d", &n, &m);
for(int i = 1, x, y, z; i <= m; ++ i)
scanf("%d%d%d", &x, &y, &z), e[i<<1] = {x, y, z}, e[i<<1|1] = {y, x, z};
sort(e+1, e+1+m*2, [](edge x, edge y){return x.z < y.z;});
if(mst()) printf("%d", ans);
else printf("orz");
return 0;
}
```
@[zhuyuhao1123](/user/526470)
by Lisuyang @ 2024-10-09 22:29:03
如果最后能够找到不止一个满足 ``findfather(i)==i`` 的 $i$，那么就无法连成一棵树
by aeiouaoeiu @ 2024-10-09 22:29:38
@[zhuyuhao1123](/user/526470)
把sum改为全局变量，```print```输出改为：
```cpp
(sum==n-1)?cout<<ans:cout<<"orz";
```
就行了，因为如果不连通，连不到 $n-1$ 条边
~~**求关**~~
by Alicezhou @ 2024-10-09 22:30:45
@[Alicezhou](/user/305735) 已关
by zhuyuhao1123 @ 2024-10-09 22:34:52
跑一遍最短路，看看有没有最短路长度仍是无穷大的
by rb_tree @ 2024-10-12 20:21:40
并查集每次合并都取编号较小的，最后看有没有节点的 ```father[i]!=1```
by dami826 @ 2024-10-25 08:42:10