image.png

解法

深度优先遍历解法

class Solution {

    private List<List<Integer>> edges = new ArrayList<>();
    // 对应课程，0代表未搜索，1代表搜索中，2代表已完成
    private int[] visited;
    private boolean valid = true;
    
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        visited = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            edges.add(new ArrayList<>());
        }
        for (int[] p: prerequisites) {
            // 节点p[1]后面的节点有多少
            edges.get(p[1]).add(p[0]);
        }
        for (int i = 0; i < numCourses; i++) {
            if (visited[i] == 0) {
                dfs(i);
            }
        }
        return valid;
    }

    public void dfs(int i) {
        visited[i] = 1;
        for (int v : edges.get(i)) {
            // 后面节点未搜索，进行搜索
            if (visited[v] == 0) {
                dfs(v);
                if (!valid) {
                    return;
                }
            } else if (visited[v] == 1) {
                // 后面节点也在搜索中，说明有环，有环则说明不是拓扑排序
                valid = false;
                return;
            }
            // 后面节点已经搜索完成，说明有其它前置节点已经搜索过，并且已经搜索完成
        }
        visited[i] = 2;
    }
}

广度优先解法

class Solution {
    
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // 每个节点的入度
        int[] inCount = new int[numCourses];
        List<List<Integer>> edges = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            edges.add(new ArrayList<>());
        }
        // 计算其中涉及到的边
        for (int[] p : prerequisites) {
            edges.get(p[1]).add(p[0]);
            inCount[p[0]]++;
        }
        // 存放入度为0的节点
        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (inCount[i] == 0) {
                q.offer(i);
            }
        }
        int size = 0;
        while (!q.isEmpty()) {
            size++;
            // 弹出入度为0的节点后，将相邻节点的入度减1
            int a = q.poll();
            List<Integer> nextList = edges.get(a);
            for (int next : nextList) {
                inCount[next] -= 1;
                // 入度为0的节点，还放到队列中
                if (inCount[next] == 0) {
                    q.offer(next);
                }
            }
        }
        return size == numCourses;
    }
}