Contents
  1. 1. 题目
    1. 1.1. eg1
    2. 1.2. eg2
  2. 2. 关键点
  3. 3. 方法
  4. 4. 实现

题目

输入二维数组,a[i][j]=1 表示从i结点指向j结点。

eg1

0 1 1 0

1 0 0 1

1 0 0 0

0 1 0 0

是一棵树,树为:

1
2
3
4
5
6
7
8
9
a
/ \
b c
/
d

eg2

0 1 1 0

1 0 0 1

1 0 1 0

0 1 1 0

不是一颗树,是有环(a-b-d-c-a)的图:

1
2
3
4
5
6
7
8
9
a
/ \
b c
/ /
d - — -

关键点

判断一张图是否是一颗树的两个关键点:

  • 不存在环路(对于有向图,不存在环路也就意味着不存在强连通子图)
  • 满足边数加一等于顶点数的规律(不考虑重边和指向自身的边)

方法

  1. DFS

  2. 如果存在回路,则必存在一个子图,是一个环路。环路中所有顶点的度>=2。时间复杂度O(ve),v是顶点数,e是边数。

    第一步:删除所有度<=1的顶点及相关的边,并将另外与这些边相关的其它顶点的度减一。

    第二步:将度数变为1的顶点排入队列,并从该队列中取出一个顶点重复步骤一。如果最后还有未删除顶点,则存在环,否则没有环。这个复杂度也很高

  3. 结合树的特性(边数+1 = 顶点数)和并查集来做,代码见下文。

实现

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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
import java.util.ArrayList;
import java.util.List;
public class TreeJudgeUnionB {
private static class Edge {
int start;
int end;
public Edge(int start, int end) {
this.start = start;
this.end = end;
}
}
// the number of edges
private int n;
// edge list
private List<Edge> edges = new ArrayList<>();
// the index of group
private int[] group;
// the size of tree
private int[] size;
public TreeJudgeUnionB(int n, List<Edge> edges) {
this.n = n;
this.edges = edges;
group = new int[n];
size = new int[n];
for (int i = 0; i < n; i++) {
group[i] = i;
size[i] = 1;
}
}
private int find(int i) {
// find the root of a tree which contains i node
while (i != group[i]) {
i = group[i];
}
return i;
}
private boolean union(int groupI, int groupJ) {
int iRoot = find(groupI);
int jRoot = find(groupJ);
if (iRoot != jRoot) {
if (size[iRoot] < size[jRoot]) {
group[iRoot] = jRoot;
size[jRoot] += size[iRoot];
} else {
group[jRoot] = iRoot;
size[iRoot] += size[jRoot];
}
return true;
} else {
return false;
}
}
public boolean isTree() {
for (Edge edge : edges) {
if (!union(edge.start, edge.end)) {
System.out.println("input two nodes in the same tree");
return false;
}
}
boolean hasRoot = false;
for (int i = 0; i < group.length; i++) {
if (i == group[i]) {
if (!hasRoot) {
hasRoot = true;
} else {
System.out.println("exist more than one tree root");
return false;
}
}
}
printGroup();
return hasRoot;
}
public void printGroup() {
for (int i = 0; i < n; i++) {
System.out.print(group[i] + ", ");
}
System.out.println();
}
public static void main(String[] args) {
int n = 5;
List<Edge> edges = new ArrayList<>();
addEdge(edges, 0, 1);
addEdge(edges, 0, 2);
addEdge(edges, 2, 3);
addEdge(edges, 2, 4);
isTree(n, edges); // true
n = 5;
edges.clear();
addEdge(edges, 0, 1);
addEdge(edges, 1, 2);
addEdge(edges, 0, 2);
addEdge(edges, 2, 3);
addEdge(edges, 2, 4);
isTree(n, edges); // false
n = 4;
edges.clear();
addEdge(edges, 0, 1);
addEdge(edges, 2, 3);
isTree(n, edges); // false
n = 7;
edges.clear();
addEdge(edges, 0, 1);
addEdge(edges, 1, 2);
addEdge(edges, 4, 5);
addEdge(edges, 3, 4);
addEdge(edges, 2, 3);
addEdge(edges, 0, 6);
isTree(n, edges); // true
}
protected static void addEdge(List<Edge> edges, int i, int j) {
edges.add(new Edge(i, j));
}
protected static void isTree(int n, List<Edge> edges) {
TreeJudgeUnionB treeJudgeUnionA = new TreeJudgeUnionB(n, edges);
boolean isTree = treeJudgeUnionA.isTree();
System.out.println("This is a tree? " + isTree);
}
}
Contents
  1. 1. 题目
    1. 1.1. eg1
    2. 1.2. eg2
  2. 2. 关键点
  3. 3. 方法
  4. 4. 实现