JavaIs It A Tree?图与培育的干

Is It A Tree?

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K
(Java/Others)
Total Submission(s): 27166    Accepted Submission(s): 6266

Problem 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 bydirected 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.

Java 1Java 2Java 3

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.


*  *HDU1325,看到网上都是连查集写的,个人感觉并查集比较费心,所以写了即首博客,闲言少叙,言归正传.

  题目要求判定所受的觊觎是否是相同株树结构,所以就待看清节点是否满足做树的尺度虽可.

明明,树不可知起环,而且干净节点的总数要也1.于凡是题材转化为对环的搜和对清节点数目的判断.这样就算得为此连查集解决这同样题.不过如果单独到此处,还免是还好的解决办法.

  事实上上述判断好转正为对节点入度的判断,显然入度为0的节点是干净节点(root),入度为1底节点是纸牌节点(leaf).

  那么树应当满足以下几单原则 :

    1.入度为0的结点的多寡也1,即到底节点数目也1.

    2.不在入度 IN > 1 的叶子节点(或者说叶子节点的入度必须 IN = 1).

  其中要在入度 IN > 1 的纸牌节点,那么是个别种植状态 :第一种植是存诸多受少数单根节点(入度 IN = 0
的节点(root) ),此时即使无做环,但强烈与规则1违背,不可知做树.

别一样种情况是独自生一个根节点,我们由此简单个入度反朝回溯,显然起星星点点种植办法回溯至同一个节点根节点.

乃我们得以判一个产生往图是写中所求的栽培结构的尽管必要条件应该是干净节点(IN = 0 的节点)数目也1, 不存在入度
IN > 1的节点.

 1 #include <bits/stdc++.h>
 2 #include <cstring>
 3 using namespace std;
 4 #define LL int
 5 LL leaf[10001];/*入度计数*/
 6 set<LL> all;/*用来记录图中所有节点, 方便的去重计数器*/
 7 int up;/*入度 IN = 1节点计数器*/
 8 bool flag;/*能否够成树*/
 9 bool in() {
10     int x, y;
11     up = 0;
12     flag = true;
13     all.clear();
14     memset(leaf, 0, sizeof(leaf));
15     while (cin >> x >> y)
16         if (x == 0 && y == 0)   {
17             if (flag)    flag = all.size() == up + 1;
18             /*如果不存在入度 IN > 1的节点,
19              那么总节点数减去up得到根节点数目
20              显然根节点数目为1时能构成树*/
21             return false;
22         }
23         else if (x == -1 && y == -1)
24             return true;
25         else if (flag){
26             leaf[y]++;
27             all.insert(x);
28             all.insert(y);
29             if (leaf[y] > 1)    flag = false;/*出现入度 IN > 1的节点*/
30             up++;/*入度是1的节点计数*/
31         }
32 }
33 int main()
34 {
35     int ctr = 0;
36     for (;;) {
37         if (in())    break;
38         cout << "Case " << ++ctr
39              << " is" << (flag ? "" : " not")
40              << " a tree." << endl;
41     }
42      return 0;
43 }

 

相关文章