检测循环依赖

算法流程

1. 先建立图的邻接表和入度表，然后选择出入度为0的节点作为起点，放入到课程学习的路径中，入度为0表示这些课程并没有前置课程，先上它们哪个都无所谓。如果没有入度为0的节点，表示有课程循环依赖，即图中有环，不存在拓扑排序，也就不存在能够完成全部课程的顺序。
2. 完成步骤1中的操作后，就可以开始拓扑排序了。每当出现一个新的入度为0的课程，就将其加入到课程学习路径中。

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param prerequisites int整型二维数组 
     * @param n int整型 
     * @return int整型一维数组
     */
    public int[] findOrder (int[][] prerequisites, int n) {
        // 建立图和入度表
        HashMap<Integer, LinkedList<Integer>> graph = new HashMap<>();
        int[] inDegree = new int[n];
        for(int i = 0; i < n; i++) graph.put(i, new LinkedList<>());
        for(int i = 0; i < prerequisites.length; i++){
            graph.get(prerequisites[i][1]).add(prerequisites[i][0]);
            inDegree[prerequisites[i][0]] ++;
        }
        Queue<Integer> queue = new LinkedList<>();
        LinkedList<Integer> list = new LinkedList<>();
        // 选择入度为0的作为起点
        for(int course = 0; course < n; course++){
            if(inDegree[course] == 0){
                list.add(course);
                queue.offer(course);
            }
        }
        // 没找到入度为0的点，存在环
        if(queue.isEmpty()) return new int[0];
        // 拓扑排序
        while(!queue.isEmpty()){
            int course = queue.poll();
            for(int neighbor: graph.get(course)){
                inDegree[neighbor] --;
                if(inDegree[neighbor] == 0){
                    // 每次将入度为0的点作为下一个起点
                    list.add(neighbor);
                    queue.offer(neighbor);
                }
            }
        }
        Iterator<Integer> iterator = list.iterator();
        int[] path = new int[n];
        for(int i = 0; i < n; i++){
            path[i] = iterator.next();
        }
        return path;
    }
}

时间复杂度

#include <vector>
#include <queue>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param prerequisites int整型vector<vector<>> 
     * @param n int整型 
     * @return int整型vector
     */
    bool toposort(int n)
    {
        queue<int> q;
        for(int i=0;i<n;i++) //n个点 首先推入入度为0的点。这里可能就把单独的节点推入队列中了
        {
            if(din[i]==0) q.push(i);
        }
        while(q.size()) //若大于0
        {
            int x = q.front(); q.pop();
            tp.push_back(x);
            //遍历儿子
            for(auto y:e[x]) 
            {
                if(--din[y]==0)//儿子入度为0，推入队中
                {
                    q.push(y);
                }
            }
        }

        return tp.size()==n;
    }
    vector<int> e[2500],tp; //记录拓扑排序
    int din[2500]; //存点x的入度
    vector<int> findOrder(vector<vector<int> >& prerequisites, int n) {
        // write code here
        memset(e,0,sizeof(e));//给数组初始化为0
        for(int i=0;i<prerequisites.size();i++)
        {
            
            e[prerequisites[i][1]].push_back(prerequisites[i][0]);//增加边
            din[prerequisites[i][0]]++;
        }
        if(!toposort(n)) return {};
        else return tp;
    }
};

思路：dfs.首先把图进行反向，然后进行拓扑排序。

import java.util.*;
public class Solution {
     Map<Integer, List<Integer>> map;
     boolean visiting[];
     Integer c = 0;
    public int[] findOrder (int[][] prerequisites, int n) {
        visiting = new boolean[n];
        map = new HashMap<>();
        for(int[] prere : prerequisites) {
            int course = prere[0];
            int preCourse = prere[1];
            if(map.get(preCourse) == null) {
                List<Integer> list = new ArrayList<>();
                map.put(preCourse, list);
            }
            map.get(preCourse).add(course);
        }
        int arr[] = new int[n];
        int index = 0;
        for(int course = 0; course < n; ++course) {
            if(!dfs(course)) return new int[] {};
            arr[index++] = c;
        }
        return arr;
    }
    public boolean dfs(Integer course) {
         if(visiting[course]) return false;
         if(map.get(course) == null) {
            return true;
         }
         visiting[course] = true;
         for(int cour: map.get(course)) {
            if(!dfs(cour)) return false;
         }
         visiting[course] = false;
         map.put(course, null);
         c = course;
         return true;
    }
}

第一个题解深度优先搜索：Bugfix

import java.util.*;

public class Solution {
    // 邻接表
    List<List<Integer>> graph;
    // 是否存在循环依赖标识
    boolean valid = true;
    //记录课程状态，0表示未访问，1表示已访问，2表示已完成
    int[] visited;
    // 记录可行的课程顺序
    int[] ans;
    // ans 数组的游标
    int idx;

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param prerequisites int整型二维数组
     * @param n int整型
     * @return int整型一维数组
     */
    public int[] findOrder (int[][] prerequisites, int n) {
        // write code here
        // 初始化邻接表
        graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
        for (int[] prerequisite : prerequisites) {
            // 行：前置课程；列：后置课程
            graph.get(prerequisite[1]).add(prerequisite[0]);
        }
        visited = new int[n];
        ans = new int[n];
        idx = n - 1;

        // 遍历所有课程，DFS
        for (int i = 0; i < n && valid; i++) {
            if (visited[i] == 0) {
                dfs(i);
            }
        }
        return valid ? ans : new int[0];
    }

    private void dfs(int i) {
        visited[i] = 1;
        // i 的后置课程
        List<Integer> list = graph.get(i);
        for (Integer j : list) {
            // 后置课程未访问，DFS
            if (visited[j] == 0) {
                dfs(j);
            } 
            // 注意
            else if (visited[j] == 2) {
                continue;
            } 
            else if (visited[i] == 1) {
                valid = false;
                return;
            }
        }
        visited[i] = 2;
        ans[idx--] = i;
    }
    // /**
    //  * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
    //  *
    //  *
    //  * @param prerequisites int整型二维数组
    //  * @param n int整型
    //  * @return int整型一维数组
    //  */
    // public int[] findOrder (int[][] prerequisites, int n) {
    //     //邻接表
    //     List<List<Integer>> graph = new ArrayList<>();
    //     //入度数组
    //     int[] indegree = new int[n];
    //     //初始化邻接表
    //     for (int i = 0; i < n; i++) {
    //         graph.add(new ArrayList<>());
    //     }
    //     for (int[] cur : prerequisites) {
    //         //给对应邻接表添加后置课程
    //         graph.get(cur[1]).add(cur[0]);
    //         //入度加1
    //         indegree[cur[0]]++;
    //     }

    //     LinkedList<Integer> queue = new LinkedList<>();
    //     //将所有入度为0的课程加入到队列
    //     for (int i = 0; i < n; i++) {
    //         if (indegree[i] == 0) {
    //             queue.offer(i);
    //         }
    //     }
    //     //如果队列为空，说明有循环依赖，直接返回空数组
    //     if (queue.size() == 0) return new int[0];

    //     int[] res = new int[n];
    //     int id = 0;
    //     while (!queue.isEmpty()) {
    //         //取出当前课程
    //         int i = queue.poll();
    //         res[id++] = i;
    //         for (int j : graph.get(i)) {
    //             //后置课程入度减一
    //             indegree[j]--;
    //             //入度为0的课程入队
    //             if (indegree[j] == 0) {
    //                 queue.offer(j);
    //             }
    //         }
    //         //如果没访问完所有课程，而队列为空，说明存在环
    //         if (id < n && queue.isEmpty()) {
    //             return new int[0];
    //         }
    //     }
    //     return res;
    // }
}