图论进阶之路-最小生成树模版

在学习最小生成树之前，我们首先得掌握写最小生成树的必要知识：

并查集

主要用于判断两个结点是否在一个集合内

并查集模版--------------------------------------------------------------------
static class UnionFind {
    int[] father;//记录祖先
    int[] size;//记录集合大小
    LinkedList stack = new LinkedList<>();//用于扁平化处理
 
    UnionFind(int n,int[][] edges){
        father = new int[n];
        size = new int[n];
        for(int i=0;i
            father[i] = i;//初始化先将所有祖先设置为自己
        }
        Arrays.fill(size,1);
    }
 
    int find(int n){
        while(father[n] != n){//不断查找祖先，直到祖先就是自己
            stack.push(n);
            n = father[n];
        }
        while(!stack.isEmpty()){
            father[stack.pop()] = n;//扁平化处理，方便下一次查找
        }
        return n;//返回祖先
    }
 
    void union(int a,int b){//找到两个结点的祖先，将较小的的集合合并到较大的集合下
        int x = find(a);
        int y = find(b);
        if(size[x] > size[y]){
            father[y] = x;
            size[x] += size[y];
        }else{
            father[x] = y;
            size[y] += size[x];
        }
    }
}

大家可以当做模版记忆，有了并查集后，我们就可以判断任意两个结点是否联通

接下来，便可以应对最小生成树的问题：

题目描述

如题，给出一个无向图，求出最小生成树，如果该图不连通，则输出 orz。

输入格式

第一行包含两个整数 𝑁,𝑀N,M，表示该图共有 𝑁N 个结点和 𝑀M 条无向边。

接下来 𝑀M 行每行包含三个整数 𝑋𝑖,𝑌𝑖,𝑍𝑖Xi​,Yi​,Zi​，表示有一条长度为 𝑍𝑖Zi​ 的无向边连接结点 𝑋𝑖,𝑌𝑖Xi​,Yi​。

输出格式

如果该图连通，则输出一个整数表示最小生成树的各边的长度之和。如果该图不连通则输出 orz。

输入输出样例

输入 #1复制

4 5
1 2 2
1 3 2
1 4 3
2 3 4
3 4 3

输出 #1复制

7

说明/提示

数据规模：

对于 20%20% 的数据，𝑁≤5N≤5，𝑀≤20M≤20。

对于 40%40% 的数据，𝑁≤50N≤50，𝑀≤2500M≤2500。

对于 70%70% 的数据，𝑁≤500N≤500，𝑀≤104M≤104。

对于 100%100% 的数据：1≤𝑁≤50001≤N≤5000，1≤𝑀≤2×1051≤M≤2×105，1≤𝑍𝑖≤1041≤Zi​≤104。

样例解释：

所以最小生成树的总边权为 2+2+3=72+2+3=7。

最短生成树的边一定是 n-1 条，若小于 n-1 条则无法保证可以连接所有结点，若大于 n-1 条则无法保证生成的树是最小的

这是一道典型的最小生成树模版题，最短生成树的思路其实很简单，就是不断拿到权值最小的边，判断两端结点是否在一个集合内，若不在，证明该边是最短生成树的一条边，其中难点就在于如何判断两端结点是否在一个集合内，但是，在学习了并查集后这个难点也变得唾手可得

我们直接套用并查集模版解决

最小生成树

import java.util.*;
 
public class Main {
    public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
    	int n = sc.nextInt();
    	int m = sc.nextInt();
    	List<int[]> power = new ArrayList<>();//记录所有权值以及边连接的结点
    	UnionFind uf = new UnionFind(n);
    	for(int i=0;i
    		int a = sc.nextInt(),b = sc.nextInt(),p = sc.nextInt();
    		power.add(new int[]{p,a,b});
    	}
    	//按照权值从小到大生成树，若遍历到的边使得生成树出现环，就不添加该边
    	Collections.sort(power,(a,b)->a[0]-b[0]);
    	long ans = 0;
    	int count = 0;
    	for(int[] a : power){
    		if(uf.find(a[1]) != uf.find(a[2])){
    			uf.union(a[1], a[2]);
    			ans += a[0];
    			count++;
    		}
    	}
    	System.out.println(count == n-1 ? ans : "orz");
    }
    static class UnionFind{
    	int[] father;
    	int[] size;
    	LinkedList stack;
    	UnionFind(int n){
    		father = new int[n+1];
    		for(int i=1;i<=n;i++)father[i] = i;
    		size = new int[n+1];
    		stack = new LinkedList<>();
    	}
    	int find(int x){
    		while(father[x] != x){
    			stack.push(x);
    			x = father[x];
    		}
    		//扁平化处理
    		while(!stack.isEmpty()){
    			father[stack.pop()] = x;
    		}
    		return x;
    	}
    	void union(int x,int y){
    		int fx = find(x);
    		int fy = find(y);
    		if(size[fx] > size[fy]){
    			father[fy] = fx;
    			size[fx] += size[fy];
    		}else{
    			father[fx] = fy;
    			size[fy] += size[fx];
    		}
    	}
    }
}

由于这是洛谷的 OJ 对 java 玩家不是很友好，代码虽然是对的，但是内存只给128MB，有三个样例会超出一点内存限制，我用GPT换成了C++语言，这个交上去就会全通过了，不过大家可以放心，在比赛和笔试的时候是不会出现这种情况的，出题人会把语言局限考虑进去的

#include 
#include 
#include 
 
using namespace std;
 
class Main {
public:
    vector<int> father;
    vector<int> size;
    vector<int> stack;
    
    Main(int n) {
        father.resize(n + 1);
        for (int i = 1; i <= n; i++) father[i] = i;
        size.resize(n + 1);
    }
    
    int find(int x) {
        while (father[x] != x) {
            stack.push_back(x);
            x = father[x];
        }
        while (!stack.empty()) {
            father[stack.back()] = x;
            stack.pop_back();
        }
        return x;
    }
    
    void Union(int x, int y) {
        int fx = find(x);
        int fy = find(y);
        if (size[fx] > size[fy]) {
            father[fy] = fx;
            size[fx] += size[fy];
        } else {
            father[fx] = fy;
            size[fy] += size[fx];
        }
    }
};
 
int main() {
    int n, m;
    cin >> n >> m;
    
    vectorint>> power;
    Main uf(n);
    
    for (int i = 0; i < m; i++) {
        int a, b, p;
        cin >> a >> b >> p;
        power.push_back({p, a, b});
    }
    
    sort(power.begin(), power.end(), [](const vector<int>& a, const vector<int>& b) {
        return a[0] < b[0];
    });
    
    long long ans = 0;
    int count = 0;
    
    for (const auto& a : power) {
        if (uf.find(a[1]) != uf.find(a[2])) {
            uf.Union(a[1], a[2]);
            ans += a[0];
            count++;
        }
    }
    if(count == n - 1){
    	cout << ans << endl;
	}else{
		cout << "orz" << endl;
	}
    return 0;
}