Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree.

For example:

Given n = 5 and edges = [[0, 1], [0, 2], [0, 3], [1, 4]], return true.

Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]], return false.

Hint:

Given n = 5 and edges = [[0, 1], [1, 2], [3, 4]], what should your return? Is this case a valid tree?

According to the definition of tree on Wikipedia: “a tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any connected graph without simple cycles is a tree.”

Note: you can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.

Union Find

树是无环的联通图，所以一个无向图做为树需满足如下条件

边的数量 = n - 1

用union find连接每一个点，不能出现两个点，已经连接的情况

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

publicbooleanvalidTree(int n, int[][] edges){

if (n <= 0 || edges == null)

returnfalse;

if (edges.length != n - 1)

returnfalse;

int[] fathers = newint[n];

for (int i = 0; i < n; i++) {

fathers[i] = i;

}

for (int[] edge : edges) {

int fax = find(fathers, edge[0]);

int fay = find(fathers, edge[1]);

if (fax == fay)

returnfalse;

fathers[fax] = fay;

}

returntrue;

}

privateintfind(int[] fathers, int x){

int fa = fathers[x];

while (fa != fathers[fa]) {

fa = fathers[fa];

}

return fa;

}

DFS

DFS和BFS都不是自己写的，有机会自己再写一下吧

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

privatebooleanvalidDFS(int n, int[][] edges){

// build the graph using adjacent list

List<Set<Integer>> graph = new ArrayList<Set<Integer>>();

for (int i = 0; i < n; i++)

graph.add(new HashSet<Integer>());

for (int[] edge : edges) {

graph.get(edge[0]).add(edge[1]);

graph.get(edge[1]).add(edge[0]);

}

// no cycle

boolean[] visited = newboolean[n];

Deque<Integer> stack = new ArrayDeque<Integer>();

stack.push(0);

while (!stack.isEmpty()) {

int node = stack.pop();

if (visited[node])

returnfalse;

visited[node] = true;

for (int neighbor : graph.get(node)) {

stack.push(neighbor);

graph.get(neighbor).remove(node);

}

}

// fully connected

for (boolean result : visited) {

if (!result)

returnfalse;

}

returntrue;

}

BFS

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

privateboolean valid(int n, int[][] edges) {

// build the graph using adjacent list

List<Set<Integer>> graph = new ArrayList<Set<Integer>>();