利用并查集求最小生成树
目录
什么是 Kruskal 算法?
Kruskal 算法是求最小生成树的一种方法,有点类似于贪心算法,首先是按照边的权值从小到大进行排序,然后不断地将较小的边加入到过程解的集合,关键是要解决回路的问题,而利用并查集就可以很好地解决这个问题,即每次添加边之前,判断该边的两个顶点是否是处于相同的集合,相同就跳过,否则加入到过程解中,重复这个过程,知道最后只有一个集合,该集合即为所求。
题目:
来源于洛谷
题目描述
如题,给出一个无向图,求出最小生成树,如果该图不连通,则输出 orz
。
输入格式
第一行包含两个整数 N,M,表示该图共有 N 个结点和 M 条无向边。
接下来 M 行每行包含三个整数 Xi, Yi, Zi,表示有一条长度为 Zi 的无向边连接结点 Xi, Yi
输出格式
如果该图连通,则输出一个整数表示最小生成树的各边的长度之和。如果该图不连通则输出 orz
。
求解:
/*
* @Author: YaleXin
* @Date: 2020-01-21 11:11:04
* @LastEditTime: 2020-04-10 22:51:47
* @LastEditors: YaleXin
* @Description:
* @FilePath: \my_c_workspace\luo_gu\P3366.c
* @祈祷不出现BUG
*/
#include <stdio.h> //利用kruskal算法
int arc[200001][3], n, m; // arc的最后一个代表权值,前两个代表邻接点
int arc_index[200001]; //存放边的编号,排序后得到的是按照边权值升序的编号
int anc[200001]; //并查集辅助数组,存放每一个点属于的集合
int find_anc(int son) {
if (anc[son] == son)
return son;
else {
//压缩路径
anc[son] = find_anc(anc[son]);
return anc[son];
}
}
void q_sort(int left, int right) {
if (left >= right) return;
int l = left, r = right, piv = arc_index[left];
while (l < r) {
while (l < r && arc[arc_index[r]][2] >= arc[piv][2]) r--;
arc_index[l] = arc_index[r];
while (l < r && arc[arc_index[l]][2] <= arc[piv][2]) l++;
arc_index[r] = arc_index[l];
}
arc_index[l] = piv;
q_sort(left, l - 1);
q_sort(r + 1, right);
}
int main() {
int i, sum = 0;
scanf("%d %d", &n, &m);
for (i = 0; i < n; i++) anc[i] = i; //刚开始每一个点是单独的集合
for (i = 0; i < m; i++) {
scanf("%d %d %d", &arc[i][0], &arc[i][1], &arc[i][2]);
arc_index[i] = i;
}
q_sort(0, m - 1); //将边的权值排序
for (i = 0; i < m; i++) { //依次把最小的边进行“并”
// 如果同属于“祖先”,则跳过
if (find_anc(arc[arc_index[i]][1]) == find_anc(arc[arc_index[i]][0]))
continue;
// 如果不同,则说明是符合,可以添加
else {
anc[find_anc(anc[arc[arc_index[i]][0]])] = arc[arc_index[i]][1];
sum += arc[arc_index[i]][2];
}
}
printf("%d", sum);
return 0;
}
/*
4 5
1 2 2
1 3 8
1 4 3
2 3 4
3 4 3
*/
本文由「黄阿信」创作,创作不易,请多支持。
如果您觉得本文写得不错,那就点一下「赞赏」请我喝杯咖啡~
商业转载请联系作者获得授权,非商业转载请附上原文出处及本链接。
关注公众号,获取最新动态!
历史评论
开始评论