判断无向图是否为树：连通且无环

本文属于「408 算法拓展训练」——考纲内、真题代码题尚未考过的经典题。并查集是「树」这一章里判断连通性、检测环的标准工具，也是最小生成树 Kruskal 算法的基础。这道题是练并查集最直接的载体。它是经典训练题，不是真题，也不押题。

题目

给定一个含 n 个顶点、m 条边的无向图，顶点编号 0 到 n−1，边用数组 edges 给出，edges[i] = [u, v] 表示 u 和 v 之间有一条边。设计一个时间上尽可能高效的算法，判断这个图是否是一棵树。

题面出现了「尽可能高效」，按拓展训练导语的分类，这道题属于「暴力→最优」型——先写对暴力解、算清楚它值多少分，再找浪费、升级最优解。

判定条件是图论里的基本事实：无向图是树，当且仅当它连通且无环；换一个等价说法，当且仅当它恰有 n−1 条边、且连通。这两个说法后面都会用到。

第一步：把暴力解写对——加边时逐次判连通

最直接的想法：把 m 条边一条一条加入图中，每加一条边之前，先检查这条边的两个端点是不是已经连通——如果已经连通，说明再加这条边会构成环，图不是树，直接返回假；如果不连通，就正常加入这条边，继续处理下一条。全部边加完还没发现环，且边数恰好是 n−1，就是一棵树。

#define MAXV 100

int connectedBFS(int graph[][MAXV], int n, int u, int v) {
    int visited[MAXV] = {0};
    int queue[MAXV], front = 0, rear = 0;
    queue[rear++] = u;
    visited[u] = 1;
    while (front < rear) {
        int cur = queue[front++];
        if (cur == v) return 1;
        for (int j = 0; j < n; j++)
            if (graph[cur][j] && !visited[j]) {
                visited[j] = 1;
                queue[rear++] = j;
            }
    }
    return 0;
}

int isTreeBrute(int n, int edges[][2], int m) {
    if (m != n - 1) return 0;              // 边数不对，不可能是树
    int graph[MAXV][MAXV] = {0};
    for (int i = 0; i < m; i++) {
        int u = edges[i][0], v = edges[i][1];
        if (connectedBFS(graph, n, u, v)) return 0;   // 已连通，加入会成环
        graph[u][v] = graph[v][u] = 1;
    }
    return 1;
}

拿 n=5、edges = [[0,1],[0,2],[0,3],[1,4]] 走一遍：先判 m=4=n−1，通过。加边 0-1 前 0、1 互不连通，加入；加边 0-2、0-3 同理都能加入；加边 1-4 前，1 和 4 也不连通（图中还没有到 4 的路），加入。四条边都顺利加完，返回真——确实是一棵树。

复杂度：每条边加入前做一次 BFS，一次 BFS 最坏 $O(V+E)$，m 条边总共 $O(V\cdot E)$；空间上邻接矩阵占 $O(n^2)$，BFS 的访问数组和队列占 $O(n)$。

它值多少分

用总纲的两维度看：

• 正确性：判定条件用对了（边数 = n−1 且加边过程无环），BFS 判连通的实现也是标准写法，结果正确、复杂度分析和实现一致。正确性维度的分拿得到。
• 最优性：题面要求「尽可能高效」，$O(V\cdot E)$ 对于这道图论题不是最优。用并查集能把整体检测降到近乎线性，这一档还有提升空间。

暴力解的浪费在哪

用总纲的「找浪费三问」审一遍：

有没有重算已知的东西？——有。 每加一条边就重新发起一次 BFS，去判断两个端点是否连通，而这次 BFS 会把当前图里所有已经确认连通的顶点重新走一遍——这些连通关系其实在前几步加边时已经确定下来了，只是暴力解没有把它们「记住」，每次都要从头重新探路。

具体一点：加完前 k 条边之后，图已经天然分成若干个连通块，「两个顶点是否连通」这个问题的答案，本质上只取决于它们分别属于哪个连通块——块的归属关系是一个可以增量维护的状态，不需要每次都靠一次完整的图遍历去现场推导。

浪费的本质：每条边都用一次全图 BFS 重新计算连通性，而连通性这个信息本可以随着加边过程被增量地记录和更新。

智慧化改造：并查集维护集合归属

对策是总纲里的第二类手段——把中间结果存下来。这里存的是每个顶点当前所在的连通块，用并查集的 parent 数组维护：初始时每个顶点自成一个集合；每加入一条边 (u, v)，先找到 u、v 各自所在集合的代表元（根），如果两个根相同，说明 u、v 已经在同一个连通块里，这条边加入就会成环；如果根不同，就把两个集合合并成一个。

int find(int parent[], int x) {
    while (parent[x] != x) {
        parent[x] = parent[parent[x]];    // 路径压缩（隔代压缩），加速后续查找
        x = parent[x];
    }
    return x;
}

int isTreeUnionFind(int n, int edges[][2], int m) {
    if (m != n - 1) return 0;
    int parent[MAXV];
    for (int i = 0; i < n; i++) parent[i] = i;    // 初始时每个顶点各自一个集合

    for (int i = 0; i < m; i++) {
        int ru = find(parent, edges[i][0]);
        int rv = find(parent, edges[i][1]);
        if (ru == rv) return 0;           // 同一集合，加入会成环
        parent[ru] = rv;                  // 合并两个集合
    }
    return 1;                             // 边数=n-1 且加边过程无环
}

从暴力解升级过来，几处最容易翻车：

• 判环的动作从「BFS 探路」变成了「查两个根是否相同」，这是并查集省下暴力解那次重复扫描的关键——find 只沿着 parent 链走到根，不需要像 BFS 那样把整个连通块的顶点都摸一遍。
• 路径压缩是让并查集跑得快的核心，别省。 不做路径压缩，find 在退化情况下（parent 链拉成一条长链）会退化到 $O(n)$，整体退回暴力解的量级；带路径压缩（配合按秩合并可以更进一步）之后，单次操作的均摊复杂度接近常数。
• 最后不需要再单独做一次「是否全部连通」的检查。 判树的等价条件是「恰 n−1 条边 且 无环」；而图论里有一个基本事实——n 个顶点、n−1 条边、且不含环的图，必然是连通的（一个不含环、有 c 个连通分量的图恰好有 n−c 条边，边数是 n−1 就意味着 c=1）。所以只要边数检查通过、且加边过程中每一步的 find 都没有发现「两端已同根」，就足以断定这是一棵树，不用再补一遍全图连通性扫描。这条性质容易被忽略，导致有人多写一次冗余的最终检查。

复杂度：n−1 次 find+union，配合路径压缩，均摊复杂度是反阿克曼函数量级，写成 $O(E\cdot \alpha (n))$，实践中几乎是常数；parent 数组占 $O(n)$ 空间。相比暴力解的 $O(V\cdot E)$，是数量级的提升。

两版对照跑一遍

同一组输入 n=5、edges = [[0,1],[0,2],[0,3],[1,4]]（是一棵以 0 为中心的树）。先看暴力解——每加一条边都重新发起一次 BFS 判连通：

加载可视化中...

再看并查集——每加一条边只查两个根是否相同：

加载可视化中...

演示为 JavaScript 版本，逻辑与上文 C 代码一一对应。

等价方法与升级空间

• 也可以用一次全图 DFS/BFS 代替并查集：先检查边数是否为 n−1，再从任意一个顶点出发做一次遍历，如果能访问到全部 n 个顶点，就说明连通（配合边数=n−1，同样能推出无环）。这个写法同样是 $O(V+E)$，和并查集是同一量级的等价解，只是「记录状态」的方式从并查集换成了一次遍历。
• 按秩合并：本文的并查集只做了路径压缩，如果再加上「合并时把矮树接到高树下面」的按秩合并，最坏情况下的树高会被进一步压低，两者结合是并查集的标准配置，408 大纲对这一优化点也有覆盖。

下一步

• 回到方法论源头：「暴力解到最优解」真题专题总纲