261 Graph Valid Tree

1. Question

Givennnodes labeled from0ton - 1and 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:
Givenn = 5andedges = [[0, 1], [0, 2], [0, 3], [1, 4]], returntrue.
Givenn = 5andedges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]], returnfalse.
Note: you can assume that no duplicate edges will appear inedges. Since all edges are undirected,[0, 1]is the same as[1, 0]and thus will not appear together inedges.

2. Implementation

(1) BFS
1
class Solution {
2
public boolean validTree(int n, int[][] edges) {
3
List<Set<Integer>> adjList = new ArrayList<>();
4
5
for (int i = 0; i < n; i++) {
6
adjList.add(new HashSet<>());
7
}
8
9
for (int[] edge : edges) {
10
adjList.get(edge[0]).add(edge[1]);
11
adjList.get(edge[1]).add(edge[0]);
12
}
13
14
boolean[] visited = new boolean[n];
15
Queue<Integer> queue = new LinkedList<>();
16
queue.add(0);
17
18
while (!queue.isEmpty()) {
19
int curNode = queue.remove();
20
21
// found loop
22
if (visited[curNode]) {
23
return false;
24
}
25
26
visited[curNode] = true;
27
28
for (int nextNode : adjList.get(curNode)) {
29
queue.add(nextNode);
30
adjList.get(nextNode).remove(curNode);
31
}
32
}
33
34
for (boolean e : visited) {
35
if (!e) {
36
return false;
37
}
38
}
39
return true;
40
}
41
}
Copied!
(2) DFS
1
class Solution {
2
public boolean validTree(int n, int[][] edges) {
3
List<Set<Integer>> adjList = new ArrayList<>();
4
5
for (int i = 0; i < n; i++) {
6
adjList.add(new HashSet<>());
7
}
8
9
for (int[] edge : edges) {
10
adjList.get(edge[0]).add(edge[1]);
11
adjList.get(edge[1]).add(edge[0]);
12
}
13
14
boolean[] visited = new boolean[n];
15
16
// Check if graph has cycle
17
if (hasCycle(0, visited, adjList, -1)) {
18
return false;
19
}
20
21
// Check if graph is connected
22
for (int i = 0; i < n; i++) {
23
if (!visited[i]) {
24
return false;
25
}
26
}
27
return true;
28
}
29
30
public boolean hasCycle(int node, boolean[] visited, List<Set<Integer>> adjList, int parent) {
31
visited[node] = true;
32
33
for (int nextNode : adjList.get(node)) {
34
// (1) If nextNode is visited but it is not the parent of the curNode, then there is cycle
35
// (2) If nextNode is not visited but we still find the cycle later on, return true;
36
if ((visited[nextNode] && parent != nextNode) || (!visited[nextNode] && hasCycle(nextNode, visited, adjList, node))) {
37
return true;
38
}
39
}
40
return false;
41
}
42
}
Copied!
(3) Union Find
1
class Solution {
2
public boolean validTree(int n, int[][] edges) {
3
UnionFind uf = new UnionFind(n);
4
5
for (int[] edge : edges) {
6
// Find Loop
7
if (!uf.union(edge[0], edge[1])) {
8
return false;
9
}
10
}
11
// Make sure the graph is connected
12
return uf.count == 1;
13
}
14
15
class UnionFind {
16
int[] sets;
17
int[] size;
18
int count;
19
20
public UnionFind(int n) {
21
sets = new int[n];
22
size = new int[n];
23
count = n;
24
25
for (int i = 0; i < n; i++) {
26
sets[i] = i;
27
size[i] = 1;
28
}
29
}
30
31
public int find(int node) {
32
while (node != sets[node]) {
33
node = sets[node];
34
}
35
return node;
36
}
37
38
public boolean union(int i, int j) {
39
int node1 = find(i);
40
int node2 = find(j);
41
42
if (node1 == node2) {
43
return false;
44
}
45
46
if (size[node1] < size[node2]) {
47
sets[node1] = node2;
48
size[node2] += size[node1];
49
}
50
else {
51
sets[node2] = node1;
52
size[node1] += size[node2];
53
}
54
--count;
55
return true;
56
}
57
}
58
}
Copied!

3. Time & Space Complexity

BFS: 时间复杂度O(n), 空间复杂度O(n)
DFS: 时间复杂度O(n), 空间复杂度O(n)
Union Find: 时间复杂度O(n), 空间复杂度O(n)