There are a total of n courses you have to take, labeled from 0 to n - 1.
Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]
Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?
For example:
2, [[1,0]]
There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.
2, [[1,0],[0,1]]
There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.
解题思路一：
把每个节点放到图里，然后对每个节点进行BFS，如果出现自环，则为false，否则返回true，JAVA实现如下：
static public boolean canFinish(int numCourses, int[][] prerequisites) {
if (prerequisites.length == 0 || prerequisites[0].length == 0)
return true;
HashMap<Integer, UndirectedGraphNode> hm = new HashMap<Integer, UndirectedGraphNode>();
for (int[] nums : prerequisites)
for (int i = 0; i < nums.length - 1; i++) {
if (!hm.containsKey(nums[i]))
hm.put(nums[i], new UndirectedGraphNode(nums[i]));
if (!hm.containsKey(nums[i + 1]))
hm.put(nums[i + 1], new UndirectedGraphNode(nums[i + 1]));
hm.get(nums[i]).neighbors.add(hm.get(nums[i + 1]));
}
Iterator<Integer> iterator = hm.keySet().iterator();
while (iterator.hasNext())
if (haveLoop(hm.get(iterator.next())))
return false;
return true;
}
static boolean haveLoop(UndirectedGraphNode root) {
HashMap<UndirectedGraphNode, Boolean> hm = new HashMap<UndirectedGraphNode, Boolean>();
Queue<UndirectedGraphNode> queue = new LinkedList<UndirectedGraphNode>();
hm.put(root, true);
queue.add(root);
while (!queue.isEmpty()) {
UndirectedGraphNode temp = queue.poll();
for (UndirectedGraphNode temp2 : temp.neighbors) {
if (temp2 == root)
return true;
if (!hm.containsKey(temp2)) {
hm.put(temp2, true);
queue.add(temp2);
}
}
}
return false;
}
结果TLE，问题在于判断有向图是否有环的时候，对每一个节点判断其实浪费了很多时间%>_<%
Java for LeetCode 207 Course Schedule 【Unsolved】
原文：http://www.cnblogs.com/tonyluis/p/4559024.html