now let's talk about another method for finding the minimum spanning tree - Kruskal algorithm. We know that there can be no loop in the minimum spanning tree, so we skip when we encounter the edge forming the loop, but how can we until the loop is formed? At this time, we need to judge whether the two vertices are connected. The methods to judge the connection include deep search and wide search, but their efficiency is relatively low. The more efficient method is joint search.

put all vertices into a joint query set to judge whether the two vertices are connected. Just judge whether the two vertices are in the same set (i.e. whether they have a common ancestor).

let's talk about and look up the set first. When reading a connected edge (U, V), first judge whether u and V are in the same set. If so, there is no need to merge; If not, a Union operation is used to merge the sets of u and V, so that any two elements in the two sets are connected.

A very important step in joint search

void init() {//Indicates that each point is a tree with only one node int i; for (i = 1; i <= n; i++) { f[i] = i; } return; }

Then according to the given information, these trees are combined into a big tree

int main(void) { int i, x, y; scanf("%d %d", &n, &m); init(); for (i = 1; i <= m; i++) { scanf("%d %d", &x, &y);//Input connected edge merge(x, y); } for (i = 1; i <= n; i++) { if (f[i] == i) sum++; } printf("%d\n", sum);//sum represents the number of different sets return 0; }

void merge(int v, int u) { int t1, t2;//The ancestors of V and u are represented by T1 and T2 t1 = getf(v); t2 = getf(u); if (t1 != t2) {//If they are no longer in the same set f[t2] = t1;//Just merge them } return; }

//Find dad's recursive function int getf(int v) { if (f[v] == v)//The ancestor of an ancestor is himself return v; else { //Path compression. Every time the function returns, //By the way, change the ancestor of the person you meet on the road to the number of the ancestor you finally find f[v] = getf(f[v]); return f[v]; } }

because you want to sort, set the edge and weight directly as a structure

int main(void) { int count = 0;//Used to count int n, m; int sum = 0; scanf("%d %d", &n, &m);//n is the number of vertices and m is the number of edges int i; //Enter the relationship between edges for (i = 1; i <= m; i++) { scanf("%d %d %d", &e[i].u, &e[i].v, &e[i].w); } //Sort from small to large according to the weight quicksort(1, m); //Parallel query set initialization for (i = 1; i <= n; i++) f[i] = i; //Traverse all edges for (i = 1; i <= m; i++) { //Determine whether two vertices are in the same set if (merge(e[i].u, e[i].v)) {//If the description is not in the same set, this edge can be selected count++; sum += e[i].w; } if (count == n - 1) break; } printf("%d\n", sum); return 0; }

Next is the complete Kruskal algorithm

#include<stdio.h> int f[1000]; struct edge { int u, v, w;//Two vertices, one weight }; struct edge e[10];//Define structure array void quicksort(int left, int right) { struct edge t; int i, j, mid; i = left, j = right; mid = e[(left + right) / 2].w; do { while (e[i].w < mid) i++; while (e[j].w > mid) j--; if (i <= j) { t = e[i]; e[i] = e[j]; e[j] = t; i++; j--; } } while (i <= j); if (i < right) quicksort(i, right); if (left < j) quicksort(left, j); } //And look up the set to find the ancestor function int getf(int v) { if (f[v] == v)//Found an ancestor return v; else { f[v] = getf(f[v]); return f[v]; } } //Join two subset functions int merge(int u, int v) { int t1, t2; t1 = getf(u); t2 = getf(v); if (t1 != t2) {//Judge whether two points are in the same set f[t2] = t1; return 1; } return 0; } int main(void) { int count = 0;//Used to count int n, m; int sum = 0; scanf("%d %d", &n, &m);//n is the number of vertices and m is the number of edges int i; //Enter the relationship between edges for (i = 1; i <= m; i++) { scanf("%d %d %d", &e[i].u, &e[i].v, &e[i].w); } quicksort(1, m); f[i] = i; for (i = 1; i <= m; i++) { //Determine whether two vertices are in the same set if (merge(e[i].u, e[i].v)) {//If the description is not in the same set, this edge can be selected count++; sum += e[i].w; } if (count == n - 1) //Parallel query set initialization for (i = 1; i <= n; i++) break; } printf("%d\n", sum); return 0; }