Finding minimum spanning tree by using union search set

What is? Kruskal Algorithm ？

Kruskal Algorithm is a method to find the minimum spanning tree , It is similar to greedy algorithm , First, sort the edges according to their weights from small to large , Then the smaller edges are added to the set of process solutions , The key is to solve the problem of the circuit , And we can solve this problem by using the union search set , That is, before each edge is added , Determine whether the two vertices of the edge are in the same set , Same, skip , Otherwise, it is added to the process solution , Repeat the process , Know that there is only one set at the end , The set is the desired .

subject ：

originate Luogu

Title Description

As the title , Give an undirected graph , Find the minimum spanning tree , If the graph is not connected , The output orz.

Input format

The first line contains two integers N,M, Indicates that the graph has in common N A node and M Undirected edge .

Next M Each row contains three integers Xi, Yi, Zi, It means that there is a length of Zi The undirected edge connection node of Xi, Yi

Output format

If the graph is connected , Then output an integer representing the sum of the lengths of the edges of the minimum spanning tree . If the graph is not connected, the output is orz.

solve ：

/*
 * @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
 * @ Prayer does not appear BUG
 */
#include <stdio.h>  // utilize kruskal Algorithm 
int arc[200001][3], n, m;  // arc The last of represents the weight , The first two represent adjacency points 
int arc_index[200001];  // Number of storage side , After sorting, you get the number in ascending order according to the edge weight 
int anc[200001];  // And look up the auxiliary array , Store the set to which each point belongs 
int find_anc(int son) {
    if (anc[son] == son)
        return son;
    else {
        // Compress path 
        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;  // At first each point is a separate set 
    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);          // Sort the weights of the edges 
    for (i = 0; i < m; i++) {  // The smallest edge in turn “ and ”
        //  If both belong to “ The ancestors ”, Then skip 
        if (find_anc(arc[arc_index[i]][1]) == find_anc(arc[arc_index[i]][0]))
            continue;
        //  If different , It means that it conforms to , You can add 
        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
*/

Copy