AcWing题目链接
Kruskal算法
把所有边按照边权从小到大排序把边权最小的两个顶点使用并查集加入同一个集合
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std
;
const int M
= 2e5+5;
int root
[M
];
struct edge
{
int a
, b
, c
;
bool operator < (const edge
&a
)const{
return c
< a
.c
;
}
}E
[M
];
int n
, m
;
int find(int x
){
if(root
[x
] != x
) root
[x
] = find(root
[x
]);
return root
[x
];
}
int main(){
scanf("%d%d", &n
, &m
);
int a
, b
, c
;
for(int i
= 0; i
< m
; i
++){
scanf("%d%d%d", &a
, &b
, &c
);
E
[i
]={a
,b
,c
};
}
sort(E
, E
+ m
);
int res
= 0, cnt
= 0;
for(int i
= 0; i
<= n
; i
++) root
[i
] = i
;
for(int i
= 0; i
< m
; i
++){
a
= E
[i
].a
, b
= E
[i
].b
, c
= E
[i
].c
;
int fa
= find(a
);
int fb
= find(b
);
if(fa
!= fb
){
root
[fb
] = fa
;
cnt
++;
res
+= c
;
}
}
if(cnt
!= n
-1) puts("impossible");
else printf("%d\n", res
);
return 0;
}
