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? Show More Hint 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.
public boolean validTree(int n, int[][] edges) {
HashMap<Integer, ArrayList<Integer>> map = new HashMap<Integer, ArrayList<Integer>>();
for(int i=; i<n; i++){
ArrayList<Integer> list = new ArrayList<Integer>();
map.put(i, list);
}
for(int[] edge: edges){
map.get(edge[]).add(edge[]);
map.get(edge[]).add(edge[]);
}
boolean[] visited = new boolean[n];
LinkedList<Integer> queue = new LinkedList<Integer>();
queue.offer();
while(!queue.isEmpty()){
int top = queue.poll();
if(visited[top])
return false;
visited[top]=true;
for(int i: map.get(top)){
if(!visited[i])
queue.offer(i);
}
}
for(boolean b: visited){
if(!b)
return false;
}
return true;
} public class Solution {
public boolean validTree(int n, int[][] edges) {
// initialize n isolated islands
int[] nums = new int[n];
Arrays.fill(nums, -);
// perform union find
for (int i = ; i < edges.length; i++) {
int x = find(nums, edges[i][]);
int y = find(nums, edges[i][]);
// 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 - ;
}
int find(int nums[], int i) {
if (nums[i] == -) return i;
return find(nums, nums[i]);
}
}