你好！我是你的金牌教练。在 NOIP/CSP 竞赛中，Kruskal 算法是图论的基础，而并查集（DSU）的效率直接决定了你是否会 TLE（超时）。

下面我将展示从基础实现到竞赛满分优化的代码演进过程。请注意观察并查集优化和边处理细节。

版本一：标准竞赛版 (Path Compression)

这是大部分参赛选手在赛场上最常用的写法。它包含了路径压缩，足以应对大部分 $10^5$ 级别的数据。

注意点：边权总和可能超过 int 范围，必须使用 long long。

#include <iostream>
#include <algorithm>
#include <cstdio>

using namespace std;

const int MAXN = 100005;
const int MAXM = 200005;

struct Edge {
    int u, v, w;
} edge[MAXM];

// 按照边权从小到大排序的比较函数
bool cmp(Edge a, Edge b) {
    return a.w < b.w;
}

int fa[MAXN];

// 核心：带路径压缩的查找
// 易错点：递归深度过大可能导致爆栈，但在NOI Linux环境下通常可通过调整解决
int find(int x) {
    if (fa[x] == x) return x;
    return fa[x] = find(fa[x]); // 路径压缩：直接让上级指向祖先
}

int main() {
    int n, m;
    if (scanf("%d %d", &n, &m) != 2) return 0;

    for (int i = 1; i <= m; i++) {
        scanf("%d %d %d", &edge[i].u, &edge[i].v, &edge[i].w);
    }

    // 1. 贪心策略：排序
    sort(edge + 1, edge + m + 1, cmp);

    // 2. 初始化并查集
    for (int i = 1; i <= n; i++) fa[i] = i;

    long long ans = 0; // 存储MST权重和
    int cnt = 0;       // 已选边的数量

    // 3. 遍历每一条边
    for (int i = 1; i <= m; i++) {
        int rootU = find(edge[i].u);
        int rootV = find(edge[i].v);

        if (rootU != rootV) { // 如果不在同一个集合，说明不形成环
            fa[rootU] = rootV; // 合并
            ans += edge[i].w;
            cnt++;
            if (cnt == n - 1) break; // 优化：选够 N-1 条边即可停止
        }
    }

    // 4. 判断连通性
    if (cnt == n - 1) printf("%lld\n", ans);
    else printf("orz\n");

    return 0;
}

版本二：极致优化满分版 (Path Compression + Rank + Fast I/O)

在更高强度的比赛（如省选或 NOI）中，如果 $M$ 的规模非常大或时间限制极紧，我们需要引入按秩合并和快速读入。

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

// 快速读入优化：针对海量数据输入
inline int read() {
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '1' ) { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

const int MAXN = 100005;
const int MAXM = 200005;

struct Edge {
    int u, v, w;
};

bool cmp(const Edge &a, const Edge &b) {
    return a.w < b.w;
}

int fa[MAXN], sz[MAXN]; // sz 用于按秩合并（记录集合大小）

int find(int x) {
    // 迭代版路径压缩（防止递归过深）
    int root = x;
    while (fa[root] != root) root = fa[root];
    while (fa[x] != root) {
        int next = fa[x];
        fa[x] = root;
        x = next;
    }
    return root;
}

void unite(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);
    if (rootX != rootY) {
        // 按秩合并：将小树合并到大树，保持树的平衡
        if (sz[rootX] < sz[rootY]) swap(rootX, rootY);
        fa[rootY] = rootX;
        sz[rootX] += sz[rootY];
    }
}

Edge edges[MAXM];

int main() {
    int n = read(), m = read();

    for (int i = 0; i < m; i++) {
        edges[i] = {read(), read(), read()};
    }

    sort(edges, edges + m, cmp);

    for (int i = 1; i <= n; i++) {
        fa[i] = i;
        sz[i] = 1;
    }

    long long total_weight = 0;
    int edge_count = 0;

    for (int i = 0; i < m; i++) {
        if (find(edges[i].u) != find(edges[i].v)) {
            unite(edges[i].u, edges[i].v);
            total_weight += edges[i].w;
            edge_count++;
            if (edge_count == n - 1) break;
        }
    }

    if (edge_count == n - 1) printf("%lld\n", total_weight);
    else printf("orz\n");

    return 0;
}

复杂度分析思考过程

1. 时间复杂度

• 排序阶段：使用 std::sort，平均复杂度为 $O(M \log M)$。这是 Kruskal 算法的主要消耗。
• 并查集操作阶段：
  • 在版本一（仅路径压缩）中，单次查找的均摊复杂度极低，但在构造出的极端特殊数据下，单次最坏可达 $O(\log N)$。
  • 在版本二（路径压缩+按秩合并）中，单次查找的均摊复杂度为 $O(\alpha(N))$。
  • 总复杂度为 $O(M \log M + M \alpha(N))$。由于 $\alpha(N) \le 4$，可以看作 $O(M \log M)$。

2. 空间复杂度

• 边存储：需要一个大小为 $M$ 的结构体数组，约 $2 \times 10^5 \times 12$ 字节 $\approx 2.4$ MB。
• 并查集存储：需要 $fa$ 和 $sz$（或 $rank$）数组，大小为 $N$，约 $10^5 \times 4 \times 2 \approx 0.8$ MB。
• 总空间：远小于 NOIP 常见的 128MB 或 256MB 限制，属于 $O(N + M)$ 空间复杂度。

时间复杂度优化建议

1. 关于排序：
   • 如果边权范围非常小（例如 $W \le 10^6$），可以考虑使用 计数排序 (Counting Sort) 或 基数排序 (Radix Sort) 将排序复杂度降至 $O(M)$，从而使整体复杂度达到线性的 $O(M \alpha(N))$。
2. 关于连通性提前跳出：
   • 在处理完一条边并成功合并后，立即检查 cnt == n - 1。在稠密图（$M \gg N$）中，这能显著减少并查集的操作次数。
3. 关于并查集的写法：
   • 虽然递归版的路径压缩（版本一）代码最简洁，但在深度极大的树中（如果没做按秩合并且数据刻意构造），可能会产生 Stack Overflow。在正式比赛中，迭代版 find（版本二）更稳健。

读题关键词总结 (MST篇)

• “最小生成树”/“最小代价连通”：直接锁定 Kruskal。
• “最大边权最小”：瓶颈生成树，等价于 MST。
• “$N$ 个点，$N-1$ 条边”：说明目标结构是一棵树。
• “不连通输出...”：记得处理 cnt < n - 1 的边界情况。

作为教练，我建议你先熟练掌握版本一的写法，并在理解“树的高度平衡”后，尝试将版本二的优化思路融入到你的代码模板中。加油！