本文共 1846 字，大约阅读时间需要 6 分钟。

给你一些点的集合，判断它们是否能构成一棵树。树的定义是一个连通的无环图，其中每个节点（除了根节点）只有一个父节点。以下是解决这个问题的详细步骤和思考过程。

问题分析

解决思路

代码实现

#include 
   
    using namespace std;#define pb push_back#define IOS ios::sync_with_stdio(false)#define se second#define fi first#define mp make_pairconst int maxn = 1e4 + 10;int father[maxn], vis[maxn], flag = true;void find(int x) {    if (father[x] != x) {        father[x] = find(father[x]);    }    return father[x];}void union(int x, int y) {    int fx = find(x), fy = find(y);    if (fx == fy) return;    if (fx < fy) {        father[fy] = fx;    } else {        father[fx] = fy;    }}int main() {    int kase = 0;    while (scanf("%d %d", &u, &v) != EOF) {        if (u == 0 && v == 0) {            int cnt = 0;            for (int i = 1; i <= maxn; ++i) {                if (vis[i] && find(i) == i) {                    cnt++;                }            }            if (cnt <= 1 && flag) {                printf("Case %d is a tree.\n", ++kase);            } else {                printf("Case %d is not a tree.\n", ++kase);            }            for (int i = 1; i <= maxn; ++i) {                father[i] = i;                vis[i] = 0;            }            flag = true;            continue;        }        int maxx = max(abs(u), abs(v));        vis[u] = vis[v] = 1;        union(u, v);    }    return 0;}
   

代码解释

优化注意事项

• 路径压缩：确保find操作高效。
• 按秩合并：减少查找次数，提升性能。
• 数据结构：使用数组实现并查集，避免递归深度过大。

通过上述方法，可以高效地判断给定点集合是否构成一棵树。

转载地址：http://yusn.baihongyu.com/