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

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

阅读量：180 次

发布时间：2019-02-28

本文共 1846 字，大约阅读时间需要 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_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;}