利用并查集求最小生成树

什么是 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
*/

复制