nyist 129 树的判定 (并查集)

树的判定nyist129

样例输入
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
样例输出
Case 1 is a tree.
Case 2 is a tree.
Case 3 is not a tree.

思路如下：

我是用HashSet存储节点的（假设节点数为N），判断是否构成一个有向树需要满足的条件如下：
1. 根节点只有一个，即入度为0的点只有一个
2. 普通节点有 N-1 个，即入度为1的点有 N-1 个
3. 不能成环。用并查集判断。 样例1 2 3 4 4 5 5 3 0 0不是一个树

正确代码：

package classical_algorithm.tree;
import java.io.*;
import java.util.Arrays;
import java.util.HashSet;

/**
 * Created by jal on 2018/5/9 0009.
 */
/*
思路：判断时候构成一个有向树需要满足的条件（假设节点数为N）：
1. 根节点只有一个，即入度为0的点只有一个
2. 普通节点有 N-1 个，即入度为1的点有 N-1 个
3. 不能成环。用并查集判断。 样例1 2 3 4 4 5 5 3 0 0不是一个树
 */
public class NYIST129JudgeTree2 {

    private static int []father = new int[10001];
    private static int []inNumber = new int[10001];
    static int cnt,T= 0;
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        while (in.nextToken() != StreamTokenizer.TT_EOF){
            int x,y;
            x = (int)in.nval;
            in.nextToken();
            y = (int)in.nval;
            if (x == -1 && y == -1){
                break;
            }
            T++;
            if (x == 0 && y == 0){
                out.print(String.format("Case %d is a tree.\n",T));
                out.flush();
                continue;
            }
            Arrays.fill(inNumber, 0);
            for(int i = 1; i <= 10000; i++){
                father[i] = i;
            }
            cnt = 0;
            boolean answer = true;
            HashSet<Integer>set = new HashSet<>();
            set.clear();
            while (x != 0 && y != 0) {
                set.add(x);
                set.add(y);
                inNumber[y] ++;
                int fx = find(x);
                int fy = find(y);
                father[fy] = fx;
                in.nextToken();
                x = (int) in.nval;
                in.nextToken();
                y = (int) in.nval;
            }
            int sum = 0,root = 0;
            for (int i : set){
                if (inNumber[i] > 1){
                    answer = false;
                }
                else if (inNumber[i] == 1){
                    sum++;
                }
                else if (inNumber[i] == 0){
                    root++;
                }
            }
            if (answer){
                if (root != 1 || sum != set.size()-1){
                    answer = false;
                }
                int c = 0;
                for (int i : set){// 判断是否含有环。样例1 2 3 4 4 5 5 3 0 0
                    if (i == find(i)){
                        c++;
                        if (c > 1){
                            answer = false;
                            break;
                        }
                    }
                }
            }
            if (answer){
                out.print(String.format("Case %d is a tree.\n",T));
                out.flush();
            }
            else out.print(String.format("Case %d is not a tree.\n",T));
            out.flush();
        }
    }

    private static int find(int x) {
        return father[x] == x ? x : (father[x] = find(father[x]));
    }

}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
  
58
  
59
  
60
  
61
  
62
  
63
  
64
  
65
  
66
  
67
  
68
  
69
  
70
  
71
  
72
  
73
  
74
  
75
  
76
  
77
  
78
  
79
  
80
  
81
  
82
  
83
  
84
  
85
  
86
  
87
  
88
  
89
  
90
  
91
  
92
  
93
  
94
  
95
  
96
  
97
  
98
 

文章来源: blog.csdn.net，作者：爱玲姐姐，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/jal517486222/article/details/80252863