力扣labuladong——一刷day78
2023-12-23 18:31:18
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档
前言
图这种数据结构有一些比较特殊的算法,比如二分图判断,有环图无环图的判断,拓扑排序,以及最经典的最小生成树,单源最短路径问题,更难的就是类似网络流这样的问题
一、力扣210. 课程表 II(DFS)
class Solution {
boolean[] onPath;
boolean[] visited;
boolean flag = false;
List<Integer> res = new LinkedList<>();
public int[] findOrder(int numCourses, int[][] prerequisites) {
onPath = new boolean[numCourses];
visited = new boolean[numCourses];
List<Integer>[] graph = builderGraph(numCourses, prerequisites);
for(int i = 0; i < numCourses; i ++){
traverse(graph,i);
}
if(flag){
return new int[]{};
}
Collections.reverse(res);
return res.stream().mapToInt(Integer::intValue).toArray();
}
public void traverse(List<Integer>[] graph, int s){
if(onPath[s]){
flag = true;
return;
}
if(visited[s] || flag){
return;
}
onPath[s] = true;
visited[s] = true;
for(int a : graph[s]){
traverse(graph, a);
}
res.add(s);
onPath[s] = false;
}
public List<Integer>[] builderGraph(int numCourses, int[][] prerequisites){
List<Integer>[] graph = new LinkedList[numCourses];
for(int i = 0; i < numCourses; i ++){
graph[i] = new LinkedList<>();
}
for(int[] arr: prerequisites){
int to = arr[0];
int from = arr[1];
graph[from].add(to);
}
return graph;
}
}
二、力扣力扣210. 课程表 II(BFS)
class Solution {
int[] degree;
public int[] findOrder(int numCourses, int[][] prerequisites) {
degree = new int[numCourses];
List<Integer>[] graph = builderGraph(numCourses, prerequisites);
Deque<Integer> deq = new LinkedList<>();
int[] res = new int[numCourses];
int count = 0;
for(int i = 0; i < numCourses; i ++){
if(degree[i] == 0){
deq.offerLast(i);
res[count++] = i;
}
}
while(!deq.isEmpty()){
int cur = deq.pollFirst();
for(int a : graph[cur]){
degree[a] --;
if(degree[a] == 0){
res[count++] = a;
deq.offerLast(a);
}
}
}
if(count != numCourses){
return new int[]{};
}
return res;
}
public List<Integer>[] builderGraph(int numCourses, int[][] prerequisites){
List<Integer>[] graph = new LinkedList[numCourses];
for(int i = 0;i < numCourses; i ++){
graph[i] = new LinkedList<>();
}
for(int[] arr : prerequisites){
int from = arr[1];
int to = arr[0];
graph[from].add(to);
degree[to] ++;
}
return graph;
}
}
文章来源:https://blog.csdn.net/ResNet156/article/details/135168428
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!