POJ——1308 HDU——Is It A Tree?（并查集模板题）-白红宇

POJ——1308 HDU——Is It A Tree?（并查集模板题）

阅读量：180 次

发布时间：2019-02-28

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

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

问题分析

树的定义：树是一个连通的无环图，每个节点（除了根节点）有且仅有一个父节点。

有向图：需要考虑方向，确保子节点是根节点的。

输入数据：多个测试用例，每个用例包含若干节点和边。

并查集：使用并查集来管理父节点关系，判断连通性和是否存在环。

解决思路

并查集初始化：每个节点的父节点初始为自身，标记数组记录节点是否被访问。

路径压缩和按秩合并：优化find和union操作，减少时间复杂度。

处理每个测试用例：

初始化父节点和访问标记。

遍历每条边，合并节点。

检查是否存在环或多个父节点。

判断结果：

如果所有节点连通且无环，且只有一个根节点，则是树。

否则，不是树。

代码实现

#include 
   
    
using namespace std;
#define pb push_back
#define IOS ios::sync_with_stdio(false)
#define se second
#define fi first
#define mp make_pair
const 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;
}