Kruskal 最小生成树模板题

📝 题目描述

给定一个无向图，包含 \(n\) 个点和 \(m\) 条边。每条边连接两个不同的顶点 \(u\) 和 \(v\)，边权为 \(w\)。请你使用 Kruskal 算法 找出这张图的最小生成树，并输出最小生成树的总权值。

如果图不连通，无法生成生成树，请输出 -1。

📥 输入格式

第一行包含两个整数 \(n\) 和 \(m\)，表示点的数量和边的数量。

接下来 \(m\) 行，每行包含三个整数 \(u, v, w\)，表示一条连接点 \(u\) 和 \(v\) 的边，边的权值为 \(w\)。

• 点从 \(1\) 编号到 \(n\)。
• 保证不存在自环（即 \(u \ne v\)），但可能存在重边。

📤 输出格式

如果存在最小生成树，输出一个整数，表示最小生成树的总权值。

否则输出 -1。

🔒 数据范围

• \(1 \leq n \leq 10^5\)
• \(1 \leq m \leq 2 \times 10^5\)
• \(1 \leq u, v \leq n\)
• \(1 \leq w \leq 10^6\)

💡 提示

使用 Kruskal 算法时，建议搭配 并查集 进行判断是否会形成环。

🧪 输入输出样例

输入样例 1

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

输出样例 1

10

解释：选取边 (1,3)=2，(1,2)=3，(3,4)=5，总权值为 10，正好连接所有点，且权值最小。

输入样例 2

4 2
1 2 1
3 4 2

输出样例 2

-1

解释：图不连通，无法构成生成树。