首页 > 代码库 > Graph Valid Tree
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? 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.
1 public boolean validTree(int n, int[][] edges) { 2 HashMap<Integer, ArrayList<Integer>> map = new HashMap<Integer, ArrayList<Integer>>(); 3 for(int i=0; i<n; i++){ 4 ArrayList<Integer> list = new ArrayList<Integer>(); 5 map.put(i, list); 6 } 7 8 for(int[] edge: edges){ 9 map.get(edge[0]).add(edge[1]);10 map.get(edge[1]).add(edge[0]);11 }12 13 boolean[] visited = new boolean[n];14 15 LinkedList<Integer> queue = new LinkedList<Integer>();16 queue.offer(0);17 while(!queue.isEmpty()){18 int top = queue.poll();19 if(visited[top])20 return false;21 22 visited[top]=true;23 24 for(int i: map.get(top)){25 if(!visited[i])26 queue.offer(i);27 }28 }29 30 for(boolean b: visited){31 if(!b)32 return false;33 }34 35 return true;36 }
Graph Valid Tree
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。