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;
}