算法理解
先将所有边按权值排序。每次选择当前最小、且两端尚不连通的边，这样不会形成环；并查集负责判断和合并连通块。
- 复杂度：
O(m log m)，瓶颈是边排序。 - 注意：若最终选边数不是
n - 1，说明图不连通，不存在生成树。
模板代码
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(),x.end()
#define int long long
using pii=pair<int,int>;
const int mod=1e9+7;
const int maxn=1e6+5;
#define lowbit(x) (x&(-x))
#define vc vector<int>
struct node
{
int x,y,z;
bool operator<(node other) const{
return z<other.z;
}
};
int f[maxn];
int find_(int x)
{
if (f[x]==x) return x;
else
{
return f[x]=find_(f[x]);
}
}
void solve()
{
int n,m;
cin>>n>>m;
for (int i=0;i<=n;i++)
{
f[i]=i;
}
vector<struct node>b(m);
for (int i=0;i<m;i++)
{
int x,y,z;
cin>>x>>y>>z;
b[i]={x,y,z};
}
sort(b.begin(),b.end());
int ans=0;
int cnt=0;
for (int i=0;i<m;i++)
{
int u = b[i].x;
int v = b[i].y;
int xx = find_(u);
int yy = find_(v);
if (xx==yy)
{
continue;
}
else
{
ans+=b[i].z;
f[xx]=yy;
cnt++;
}
}
if (cnt!=n-1)
{
cout<<"orz";
return ;
}
else
{
cout<<ans;
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t=1;
// cin>>t;
while(t--)
{
solve();
}
return 0;
}