Repository navigation
Expand file tree
/
Copy pathGraph_Valid_Tree.java
More file actions
83 lines (65 loc) · 2.81 KB
/
Copy pathGraph_Valid_Tree.java
File metadata and controls
83 lines (65 loc) · 2.81 KB
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
261. Graph Valid Tree
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.
//bfs
public class Solution {
public boolean validTree(int n, int[][] edges) {
// n must be at least 1
if (n < 1) return false;
// create hashmap to store info of edges
Map<Integer, Set<Integer>> map = new HashMap<>();
for (int i = 0; i < n; i++) map.put(i, new HashSet<>());
for (int[] edge : edges) {
map.get(edge[0]).add(edge[1]);
map.get(edge[1]).add(edge[0]);
}
// bfs starts with node in label "0"
Set<Integer> set = new HashSet<>();
Queue<Integer> queue = new LinkedList<>();
queue.add(0);
while (!queue.isEmpty()) {
int top = queue.remove();
// if set already contains top, then the graph has cycle
// hence return false
if (set.contains(top)) return false;
for (int node : map.get(top)) {
queue.add(node);
// we should remove the edge: node -> top
// after adding a node into set to avoid duplicate
// since we already consider top -> node
map.get(node).remove(top);
}
set.add(top);
}
return set.size() == n;
}
}
/////////////////////////////////////
public class Solution {
public boolean validTree(int n, int[][] edges) {
// initialize n isolated islands
int[] nums = new int[n];
Arrays.fill(nums, -1);
// perform union find
for (int i = 0; i < edges.length; i++) {
int x = find(nums, edges[i][0]);
int y = find(nums, edges[i][1]);
// if two vertices happen to be in the same set
// then there's a cycle
if (x == y) return false;
// union
nums[x] = y;
}
return edges.length == n - 1;
}
int find(int nums[], int i) {
if (nums[i] == -1) return i;
return find(nums, nums[i]);
}
}