Course Schedule ——LeetCode

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.

Note:
The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.

题目大意:给一堆课程依赖,找出是否可以顺利修完全部课程,拓扑排序。

解法一:DFS+剪枝,DFS探测是否有环,图的表示采用矩阵。

    public boolean canFinish(int n, int[][] p) {
if (p == null || p.length == 0) {
return true;
}
int row = p.length;
int[][] pre = new int[n][n];
for (int i = 0; i < n; i++) {
Arrays.fill(pre[i], -1);
}
for (int i = 0; i < row; i++) {
pre[p[i][0]][p[i][1]] = p[i][1];
}
// System.out.println(Arrays.deepToString(pre));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j) {
continue;
}
if (pre[i][j] != -1) {
Deque<Integer> queue = new ArrayDeque<>();
queue.offer(pre[i][j]);
Set<Integer> circleDep = new HashSet<>();
circleDep.add(pre[i][j]);
while (!queue.isEmpty()) {
int dep = queue.poll();
if (dep >= row) {
continue;
}
for (int k = 0; k < n; k++) {
if (pre[dep][k] == -1) {
continue;
}
if (circleDep.contains(pre[dep][k])) {
return false;
}
queue.offer(pre[dep][k]);
circleDep.add(pre[dep][k]);
pre[dep][k]=-1;
}
}
}
}
}
return true;
}

解法二:BFS,参考别人的思路,也是用矩阵表示图,另外用indegree表示入度,先把入度为0的加入队列,当队列非空,逐个取出队列中的元素,indegree[i]-1==0的继续入队列,BFS遍历整个图,用count记录课程数,如果等于给定值则返回true。

    public boolean canFinish(int n, int[][] p) {
if (p == null || p.length == 0) {
return true;
}
int[][] dep = new int[n][n];
int[] indegree = new int[n];
for(int i=0;i<p.length;i++){
if(dep[p[i][0]][p[i][1]]==1){
continue;
}
dep[p[i][0]][p[i][1]]=1;
indegree[p[i][1]]++;
}
Deque<Integer> queue = new ArrayDeque<>();
for(int i=0;i<n;i++){
if(indegree[i]==0){
queue.offer(i);
}
}
int count = 0;
while(!queue.isEmpty()){
count++;
int cos = queue.poll();
for(int i=0;i<n;i++){
if(dep[cos][i]!=0){
if(--indegree[i]==0){
queue.offer(i);
}
}
}
}
return count==n;
}
上一篇:iCloud无法导入vCard问题。fix the error when import vcard/vcf to icloud.


下一篇:C++异常安全的赋值运算符重载 【微软面试100题 第五十五题】