力扣labuladong——一刷day78

发布时间:2023年12月23日

提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档


前言


图这种数据结构有一些比较特殊的算法,比如二分图判断,有环图无环图的判断,拓扑排序,以及最经典的最小生成树,单源最短路径问题,更难的就是类似网络流这样的问题

一、力扣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
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。