首页 > Is It A Tree?
开通博客写题解
头像 issue是云哥的小迷×呀
发表于 2020-08-27 23:46:16
用什么并查集啊!! 树的定义白学了嘛!!! 根节点没有入度,其他节点有且仅有一个入度(唯一的父亲) 特判树没有节点的时候,这个很坑 #include <iostream> #include <algorithm> #include <map> using name 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 sunsetcolors
发表于 2020-08-27 09:15:06
Is It A Tree? 题目地址： https://ac.nowcoder.com/acm/problem/105905 基本思路： 并查集维护生成树的过程,每次加边时判断一下是不是会产生环,然后用存一下出现了的节点,最后判断一下这些出现了的节点是不是在一个联通块里面就行了。注意空树的情 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 东溪看水
发表于 2020-08-27 10:51:04
题目 给定由有向边连接的节点集合，判断是否是树。 多个案例，每个案例以 0 0 结束。整个输入以 -1 -1 结束。 解题思路 树有且只有一个根节点。树中每个节点不能有多个父节点。树中不能有环。具体见代码。 注意：空树是树。 C++代码 #include<iostream> #inclu 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 想玩飞盘的伊登在debug
发表于 2020-08-27 11:11:34
判断是否是一棵树需要以下条件1.只有一个根节点(保证只有一棵树)2.其他所有的节点都只有一个父亲节点(满足前两条不一定可以，因为还有可能是一个独立与这个树的环，他的所有父亲节点都只有一个，同时也不增加根节点的个数)3.不存在环(可以用并查集判断，记录他的祖父节点,当一个节点的祖父节点是自己的时候，说 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 luo想要个气球
发表于 2020-08-27 15:39:01
题意： 思路： #include <cstdio> #include <set> #include <iostream> using namespace std; const int N = 1e6 + 10; int fa[N],in[N]; int m;/ 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 sunrise__sunrise
发表于 2020-08-27 16:06:08
Solution 给你一些父子关系，判断这个些点构成的集合是否是一棵树，内存给的很小。使用并查集维护，如果集合内部合并说明形成了环，不是一棵树，多个根节点，也不是一棵树。最后注意特判一下空树的情况就可以过了。 #pragma GCC target("avx,sse2,sse3,sse4,popcnt 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 bai_qi
发表于 2020-09-02 21:05:54
题目描述A tree is a well-known data structure that is either empty (null, void, nothing) or is a set of one or more nodes connected by directed edges betw 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 昵称很长很长真是太好了
发表于 2020-08-26 16:08:26
这题之前在kuangbin的专题做到过，用的是并查集题解：这里的话判断他是不是一棵树的条件1.一棵树只有一个根节点，所以我们记录所有点的入度，入度为0的点只能有一个。2.出了根节点，其他的点入度只能为1，不然就会出现图上这种情况3.所有点都必须要联通，不连通就是多棵树。 这样的话我们用并查集来给他进 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”