2 shunfurh shunfurh 于 2017.09.16 23:35 提问

Is It A Tree?

Description

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 between nodes satisfying the following properties.

There is exactly one node, called the root, to which no directed edges point.
Every node except the root has exactly one edge pointing to it.
There is a unique sequence of directed edges from the root to each node.
For example, consider the illustrations below, in which nodes are represented by circles and edges are represented by lines with arrowheads. The first two of these are trees, but the last is not.


In this problem you will be given several descriptions of collections of nodes connected by directed edges. For each of these you are to determine if the collection satisfies the definition of a tree or not.
Input

The input will consist of a sequence of descriptions (test cases) followed by a pair of negative integers. Each test case will consist of a sequence of edge descriptions followed by a pair of zeroes Each edge description will consist of a pair of integers; the first integer identifies the node from which the edge begins, and the second integer identifies the node to which the edge is directed. Node numbers will always be greater than zero.
Output

For each test case display the line "Case k is a tree." or the line "Case k is not a tree.", where k corresponds to the test case number (they are sequentially numbered starting with 1).
Sample Input

6 8 5 3 5 2 6 4
5 6 0 0

8 1 7 3 6 2 8 9 7 5
7 4 7 8 7 6 0 0

3 8 6 8 6 4
5 3 5 6 5 2 0 0
-1 -1
Sample Output

Case 1 is a tree.
Case 2 is a tree.
Case 3 is not a tree.

1个回答

caozhy
caozhy   Ds   Rxr 2017.09.30 21:39
已采纳
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
Cocoapods reference is not a tree
改问题一般都是依赖的库出了问题,下载失败。 操作步骤:进入用户根目录下,找到/Users/用户/.cocoapods/repos/master/Specs/ 在该目录下找到对应的pod库文件,则直接修改为正式可用的就OK了! [!] Error installing FileMD5Hash [!] /usr/bin/git checkout -b activ
POJ - 1308 Is It A Tree?(并查集)
题意: 给出你每对点的链接情况,问你最后构成的是不是一棵树。 解析: 并查集。有以下几点需要判断。 1. 空树是一棵树 2. 自环不算树 3. 森林不算树 4. 构成环路的不算树 AC代码#include <cstdio> #include <cstring> #include <cmath> #include <cstdlib> using namespace st
(hdu step 5.1.2)Is It A Tree?(判断是不是一棵树)
题目:Is It A Tree?Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 850 Accepted Submission(s): 273 Problem DescriptionA tree is a well-known data stru
iOS开发中解决报错之the file had a tree conflict
在开发过程中如果是多人开发,那么我们会经常commit代码、pull代码、push代码。本人之前在merge(合并)代码的时候遇到一个冲突:the file had a tree conflict 背景: 某个分支上的代码有问题,从master上切换到有问题代码的分支上。 在分支上解决有问题的代码。 将分支上的代码merge到master上。 报错:the file had a tree c...
XGBoost: A Scalable Tree Boosting System
[ 论文阅读地址 ]1. 背景知识介绍函数的风险  给定关于XX 和YY 的空间,学习一个函数h:X→Yh:X\to Y ,函数的输入x∈Xx \in X ,输出y∈Yy \in Y。要学习函数hh,需要有样本:(x1,y1),…(xm,ym)(x_1, y_1), \dots (x_m, y_m) ,其中xi∈X,yi∈Yx_i \in X, y_i \in Y,我们的目标是学习到h(xi)h(x
PAT 1135. Is It A Red-Black Tree (30) 二叉搜索树建立 + 红黑树判断
今天PAT考完试,只做出了3道题,70分。 问题在于读题。 前两题还挺顺利,很快凭借直接做完了,花了50分钟。 第三题卡在题意误解上。  判断的是“各边是否都与 所给集合点 相连” ,而非“各点与各点”相连。 当发现真正题意后,很快就做对了。 第四题最惨,1个小时的时间,有半小时在理解题意上,很短的题目,竟然没注意到“搜索树构建”,只看到“前序序列”。。。 还有,最后其实已经写成功了,就
Is It A Tree? (并查集)
Is It A Tree? Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 1173 Accepted Submission(s): 365 Problem Descriptio
Destruction of a Tree CodeForces - 964D
题面题意给出一棵树,你可以摧毁其中度数为偶数的点,同时与之相连的点将被一起摧毁,问能否摧毁所有点,若能,还要输出方案.做法首先可以发现点数为偶数的肯定不行,因为每次删除偶数条边,因此对于一对父子,若子节点的字子树大小为奇数,则肯定先摧毁其父节点再摧毁它,反之先摧毁其父节点再摧毁它,我们可以据此得出父子间的先后关系,再进行拓扑排序即可得出答案.代码#include<iostream> #include
并查集,贪心:Color A Tree
C - Color a Tree Time Limit:1000MS    Memory Limit:30000KB    64bit IO Format:%I64d & %I64u SubmitStatus Description Bob is very interested in the data structure of a tree. A tree is a direc
hdu1325Is It A Tree?(并查集)
H - Is It A Tree? Time Limit:1000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u Submit Status Description A tree is a well-known data structure that is either empty (n