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.
Solution 1 : BFS public class Solution { public boolean validTree(int n, int[][] edges) { if(edges.length != n - 1) return false; HashMap<Integer,HashSet<Integer>> hm = new HashMap<>(); for(int[] e : edges){ hm.computeIfAbsent(e[0], k-> new HashSet<Integer>()).add(e[1]); hm.computeIfAbsent(e[1], k-> new HashSet<Integer>()).add(e[0]); } HashSet<Integer> visited = new HashSet<>(); Queue<Integer> q = new LinkedList<>(); q.offer(0); visited.add(0); while(!q.isEmpty()){ int cur = q.poll(); HashSet<Integer> subNodes = hm.getOrDefault(cur,new HashSet<Integer>()); for(int next : subNodes){ hm.get(next).remove(cur); if(visited.contains(next)) return false; visited.add(next); q.offer(next); } } return visited.size() == n; } } Solution 2 : DFS public class Solution { public boolean validTree(int n, int[][] edges) { if(edges.length != n - 1) return false; HashMap<Integer,HashSet<Integer>> hm = new HashMap<>(); for(int[] e : edges){ hm.computeIfAbsent(e[0], k-> new HashSet<Integer>()).add(e[1]); hm.computeIfAbsent(e[1], k-> new HashSet<Integer>()).add(e[0]); } HashSet<Integer> visited = new HashSet<>(); visited.add(0); dfs(visited,hm,0); return visited.size() == n; } public void dfs(HashSet<Integer> visited, HashMap<Integer,HashSet<Integer>> hm, int cur){ HashSet<Integer> subNodes = hm.getOrDefault(cur,new HashSet<Integer>()); for(int next : subNodes){ if(visited.contains(next)) return; hm.get(next).remove(cur); visited.add(next); dfs(visited,hm,next); } } } Solution 3 : Union Find public class Solution { public boolean validTree(int n, int[][] edges) { if(edges.length != n - 1) return false; int[] uf = new int[n]; Arrays.fill(uf, -1); for(int[] e : edges){ if(!union(uf,e[0],e[1])) return false; } return true; } public int find(int[] uf, int x){ if(uf[x] == -1) return x; else return uf[x] = find(uf,uf[x]); } public boolean union(int[] uf, int i1, int i2){ int r1 = find(uf, i1); int r2 = find(uf, i2); if(r1 != r2){ uf[r1] = r2; return true; } return false; } }