题目地址:https://leetcode-cn.com/probl… 题目描述:现在你总共有 n 门课需要选,记为 0 到 n-1。
在选修某些课程之前需要一些先修课程。例如,想要学习课程 0,你需要先完成课程 1,我们用一个匹配来表示他们: [0,1]
给定课程总量以及它们的先决条件,判断是否可能完成所有课程的学习?
示例 1:
输入: 2, [[1,0]] 输出: true 解释: 总共有 2 门课程。学习课程 1 之前,你需要完成课程 0。所以这是可能的。示例 2:
输入: 2, [[1,0],[0,1]]输出: false 解释: 总共有 2 门课程。学习课程 1 之前,你需要先完成课程 0;并且学习课程 0 之前,你还应先完成课程 1。这是不可能的。
解答:利用图的拓扑排序。拓扑排序是来检测图中有无环的算法。具体步骤:1 找到一个入度为 0 的点,若没有,则返回图中有环。2 删除 1 中找到的点及以它为起点的边。3 重复 1、2 直到图中所有点都被删除,此时返回图中无环。
下面的一种思路是建立类似邻接表的图,这里的邻接表保存的不是边,而是指向该点的其他点,这种算法很好理解,但是时间复杂度过大。思想是,每一次都找到一个点,这个点没有任何点指向它。然后把它删除。再遍历图,把这个点作为起点的边 (其他点邻接表的元素) 删除,直到图为空返回 true 或者找不到这个点,返回 false。java ac 代码:
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
// 邻接表,存放的是指向该节点的其他节点编号,而不是边
// 如果某个点没有其他点指向它,那么对应的 list 为空。
HashMap<Integer,List<Integer>> map = new HashMap(numCourses);
for(int i = 0;i < numCourses;i++)
map.put(i,new ArrayList());
for(int i = 0;i < prerequisites.length;i++)
{
int previous = prerequisites[i][1];
int latter = prerequisites[i][0];
List<Integer>list = map.get(latter);
list.add(previous);
}
while(map.size() > 0)
{
// 判断是否能找到一个没有任何节点指向的节点
boolean flag = false;
int num = 0;
for(Map.Entry<Integer,List<Integer>> entry:map.entrySet())
if(entry.getValue().size() == 0)
{
flag = true;
num = entry.getKey();
break;
}
if(!flag)return false;
map.remove(num);
Iterator<List<Integer>> it = map.values().iterator();
while(it.hasNext())
it.next().remove(new Integer(num));
}
return true;
}
}
下面这种是利用一个队列暂存入度为 0 的点的快速拓扑排序方法。因为它不必每次都从头查找入度为 0 的点,因此时间效率得到了提示。java ac 代码:
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
// 邻接表, 表示法
HashMap<Integer,List<Integer>> map = new HashMap(numCourses);
// 存放每个点的入度,初始为 0
HashMap<Integer,Integer>map2 = new HashMap(numCourses);
for(int i = 0;i < numCourses;i++){
map.put(i,new ArrayList());
map2.put(i,0);
}
// 构造邻接表,并求出每个点的初始入度。
for(int i = 0;i < prerequisites.length;i++)
{
int previous = prerequisites[i][1];
int latter = prerequisites[i][0];
List<Integer>list = map.get(previous);
list.add(latter);
map.put(previous,list);
map2.put(latter,map2.get(latter)+1);
}
// 暂存入度为 0 的节点。
ArrayDeque<Integer>queue = new ArrayDeque();
for(int i = 0;i < numCourses;i++)
if(map2.get(i) == 0)
queue.offer(i);
// 统计最终能有多少个入度为 0 的点,若该数量小于 numCourses 则代表有环
int count = 0;
while(!queue.isEmpty())
{
int node = queue.poll();
for(int i:map.get(node))
{
int ii = map2.get(i);
ii -= 1;
if(ii != 0)
map2.put(i,ii);
// 这个点的入度变为了 0,可以加入队列中
else
queue.offer(i);
}
count++;
}
return count == numCourses;
}
}