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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
|
import java.lang.*;
import java.util.*;
import node.*;
class CourseSchedule {
public static boolean detectCycle(GraphNode node) {
Stack<GraphNode> stack = new Stack<GraphNode>();
ArrayList<GraphNode> visited = new ArrayList<GraphNode>();
stack.push(node);
while (!stack.empty()) {
node = stack.pop();
if (visited.contains(node)) {
System.out.println("Cycle " + node.val);
return true;
}
visited.add(node);
System.out.println("Node: " + node.val);
System.out.print("Neighbors: ");
for (GraphNode neighbor : node.neighbors) {
stack.push(neighbor);
System.out.print(neighbor.val + " ");
}
System.out.println();
}
return false;
}
public static GraphNode createGraph(int[][] prerequisites) {
HashMap<Integer, GraphNode> map = new HashMap<Integer, GraphNode>();
for (int[] prerequisite : prerequisites) {
if (map.containsKey(prerequisite[0])) {
if (map.containsKey(prerequisite[1])) {
map.get(prerequisite[0]).neighbors.add(map.get(prerequisite[1]));
} else {
GraphNode node = new GraphNode(prerequisite[1]);
map.put(node.val, node);
map.get(prerequisite[0]).neighbors.add(node);
}
continue;
}
GraphNode pre = new GraphNode(prerequisite[1]);
GraphNode node = new GraphNode(prerequisite[0],
new ArrayList<GraphNode>(Arrays.asList(pre)));
map.put(pre.val, pre);
map.put(node.val, node);
}
// TODO: return first GraphNode in map
return map.get(1);
}
public static boolean canFinish(int[][] prerequisites) {
GraphNode node = createGraph(prerequisites);
return !detectCycle(node);
}
public static void main(String[] args) {
int[][] prerequisites = {{1, 4}, {1, 2}, {2, 3}, {3, 6}, {6, 2}, {4, 5}};
System.out.println(canFinish(prerequisites));
}
}
|
