bulutmf
BAN USERThis is for a directed graph:
public static void main(String[] args) {
int[] vertices = {1,2,3,4,5};
HashMap<Integer, int[]> adjList = new HashMap<>();
adjList.put(1, new int[]{2});
adjList.put(2, new int[]{3,4});
adjList.put(4, new int[]{5});
System.out.println("Is tree: " + (isTree(vertices, adjList)?"yes":"no"));
}
private static boolean isTree(int[] vertices, HashMap<Integer, int[]> adjList) {
HashMap<Integer, Boolean> visited = new HashMap<>();
Stack<Integer> stack = new Stack<>();
stack.push(vertices[0]);
while (!stack.isEmpty()) {
int node = stack.pop();
visited.put(node, true);
int[] adjNodes = adjList.get(node);
if (adjNodes != null) {
for (int n : adjNodes) {
if (visited.containsKey(n)) {
return false;
}
stack.push(n);
}
}
}
for (int n : vertices) {
if (!visited.containsKey(n))
return false;
}
return true;
}
RepRussBDycus, Android test engineer at ABC TECH SUPPORT
I am working as a manager in Lionel Kiddie City company. I really enjoy my job. I like to play ...
This can be easily solved with dynamic programming. Same logic as in max subarray problem.
- bulutmf April 04, 2014