[leetcode]Graph Valid Tree

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

public class Solution { public boolean validTree(int n, int[][] edges) { if (n == 1) return true; HashMap<Integer, List<Integer>> lookup = new HashMap<Integer, List<Integer>>(); for (int i = 0; i < edges.length; i++){ List<Integer> neighbors = lookup.containsKey(edges[i][0])? lookup.get(edges[i][0]):new ArrayList<Integer>(); neighbors.add(edges[i][1]); List<Integer> neighbors2 = lookup.containsKey(edges[i][1])? lookup.get(edges[i][1]):new ArrayList<Integer>(); neighbors2.add(edges[i][0]); lookup.put(edges[i][0], neighbors); lookup.put(edges[i][1], neighbors2); } if (lookup.size() != n) return false; boolean visited[] = new boolean[n]; if (hasCycle(lookup, visited, -1, 0)) return false; for (int i = 0; i < visited.length; i++){ if (!visited[i]) return false; } return true; } public boolean hasCycle(HashMap<Integer, List<Integer>> neighbors, boolean[] visited, int parent, int current){ if (visited[current]) return true; visited[current] = true; List<Integer> neighbor = neighbors.get(current); for (int i = 0; i < neighbor.size(); i++){ if (neighbor.get(i) != parent && hasCycle(neighbors, visited, current, neighbor.get(i))){ return true; } } return false; } }