https://www.yuque.com/xiaoxiaoxcaihua/cqqo4i/loi6rn#GrOXj

拓扑排序

• 先从入度为0的点， 这些点在拓扑排序中就应该排在前面， 然后擦掉这些点的影响

• 剩下的点中就会出现下一轮入度为0的点

至此，拓扑排序完成，

如果队列中的数量没有达到图的原始数量，则false

 public boolean canFinish(int numCourses, int[][] prerequisites) {
        if (prerequisites == null || prerequisites.length == 0) {
            return true;
        }
        HashMap<Integer, Node> nodes = new HashMap<>();
        // 先把图建好
        for (int[] prerequisite : prerequisites) {
            int to = prerequisite[0];
            int from = prerequisite[1];
            if (!nodes.containsKey(to)) {
                nodes.put(to, new Node(to));
            }
            if (!nodes.containsKey(from)) {
                nodes.put(from, new Node(from));
            }
            Node t = nodes.get(to);
            Node f = nodes.get(from);
            f.nexts.add(t);
            t.in++;
        }
        int needNum = nodes.size();
        Queue<Node> zeroInQueue = new LinkedList<>();
        for (Node node : nodes.values()) {
            if (node.in == 0) {
                zeroInQueue.offer(node);
            }
        }
        int count = 0;
        while (!zeroInQueue.isEmpty()) {
            Node cur = zeroInQueue.poll();
            count++;
            for (Node next : cur.nexts) {
                if (--next.in == 0) {
                    zeroInQueue.add(next);
                }
            }
        }
        return count == needNum;
    }
    // 一个node，就是一个课程
    // name是课程的编号
    // in是课程的入度
    public static class Node {
        public int name;
        public int in;
        public ArrayList<Node> nexts;
        public Node(int n) {
            name = n;
            in = 0;
            nexts = new ArrayList<>();
        }
    }

深度优先搜索

思路

我们可以将深度优先搜索的流程与拓扑排序的求解联系起来，用一个栈来存储所有已经搜索完成的节点。

对于一个节点 u，如果它的所有相邻节点都已经搜索完成，那么在搜索回溯到 u 的时候，u 本身也会变成一个已经搜索完成的节点。这里的「相邻节点」指的是从 u 出发通过一条有向边可以到达的所有节点。

假设我们当前搜索到了节点 u，如果它的所有相邻节点都已经搜索完成，那么这些节点都已经在栈中了，此时我们就可以把 u 入栈。可以发现，如果我们从栈顶往栈底的顺序看，由于 u 处于栈顶的位置，那么 u 出现在所有 uu 的相邻节点的前面。因此对于 u 这个节点而言，它是满足拓扑排序的要求的。

这样以来，我们对图进行一遍深度优先搜索。当每个节点进行回溯的时候，我们把该节点放入栈中。最终从栈顶到栈底的序列就是一种拓扑排序。

class Solution {
 //法二：深度优先搜索
    //邻居表
    List<List<Integer>> nexts;
    // 记录节点状态 0：未搜索  1：正在搜索  2：搜索完成
    int[] visited;
    boolean valid = true;// 有环时就变成false

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        if (prerequisites == null || prerequisites.length == 0) {
            return true;
        }
        nexts = new ArrayList<>();
        visited = new int[numCourses];


        for (int i = 0; i < numCourses; i++) {
            nexts.add(new ArrayList<Integer>());
        }

        for (int[] info : prerequisites) {
            nexts.get(info[1]).add(info[0]);
        }
        for (int i = 0; i < numCourses && valid; i++) {
            if (visited[i] == 0) {//未搜索
                dfs(i);
            }
        }
        return valid;
    }

    private void dfs(int u) {
        visited[u] = 1;
        for (int v : nexts.get(u)) {
            if (visited[v] == 0) {
                dfs(v);
                if (!valid) {
                    return;
                }
            } else if (visited[v] == 1) {//搜索中
                valid = false;
                return;
            }
        }
        visited[u] = 2; //搜索完成
    }

}