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;
}
}
|
No comments:
Post a Comment