java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完):https://blog.csdn.net/grd_java/article/details/123063846 |
---|
这道题是207题的衍生题,代码完全一样,具体解析看207题即可,这里不做过多赘述了。
🏆LeetCode207. 课程表(拓扑排序)https://blog.csdn.net/grd_java/article/details/137561889 |
---|
深度优先遍历但不进行逆拓扑排序(不用栈)
解题思路:时间复杂度O(
m
+
n
m+n
m+n),空间复杂度O(
m
+
n
m+n
m+n)n是顶点数,m是边的数量 |
---|
- 有了207题的基础,我们知道,深度优先遍历的拓扑排序输出结果是逆拓扑排序
- 如果我们想要正着输出,目前经典的解决方法,是先将结果放入栈中,最后完成排序后,再次出栈完成输出,实现逆拓扑排序反转效果
- 但是我们不使用栈如何实现呢?那就是逆中逆的思路
- 我们保存所有顶点的直接前驱顶点(指向它的顶点),然后逆过了,从每个顶点向上深度优先遍历,将它所有的前驱顶点处理完成,当前顶点就是0入度顶点
- 这样就完成了深度优先遍历,直接按照正拓扑排序顺序输出的效果
- 具体可以看207题的解析,有详细案例
class Solution {
static class Node {
Node next;
int val;
public Node(){
this.val = -1;
}
public Node(int val){
this.val = val;
}
public Node(int val,Node next){
this.val = val;
this.next = next;
}
}
Node[] corses;
int[] visited;
int[] ans;
int ansIndex;
public int[] findOrder(int numCourses, int[][] prerequisites) {
corses = new Node[numCourses];
visited = new int[numCourses];
ans = new int[numCourses];
ansIndex = 0;
for(int[] corse:prerequisites){
corses[corse[0]]=new Node(corse[1],corses[corse[0]]);
}
for(int i = 0; i < numCourses; i++){
if(!dfs(i)) return new int[]{};
}
return ans;
}
private boolean dfs(int i){
if(visited[i] == 2)return true;
if(visited[i] == 1)return false;
visited[i] = 1;
Node node = corses[i];
while(node!=null){
if(!dfs(node.val)) return false;
node = node.next;
}
visited[i] = 2;
ans[ansIndex++] = i;
return true;
}
}