题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=200010;
int n,e;
int f[N];
struct edge{
int a,b,w;
bool operator<(const edge &W) const{
return w<W.w;
}
}edges[N];
int find(int x){
if(f[x]!=x) f[x]=find(f[x]);//并查集
return f[x];
}
int main(){
cin>>n>>e;
int a,b,w;
for(int i=1;i<=e;i++){
scanf("%d%d%d",&a,&b,&w);
edges[i]={a,b,w};
}
sort(edges+1,edges+e+1);
for(int i=1;i<=n;i++) f[i]=i;
int res=0,cnt=0;
for(int i=1;i<=e;i++){
a=edges[i].a,b=edges[i].b,w=edges[i].w;
int A=find(a),B=find(b);
if(A!=B){
f[A]=B;
cout<<a<<" "<<b<<endl; // 直接输出 a,b城市即可。
}
}
return 0;
}