You must take numCourses this semester, marked 0 to numcourses-1.

Some prerequisite courses are required before you can take certain courses. Prerequisites Prerequisites Prerequisites for system system system 2005: System system for System System 2005: System system for System System 2005: System system for System System 2005: System system for System System 2005: System system for system System 2005

For example, advanced Placement for [0, 1] means: In order to take course 0, you need to complete Course 1. Would you please judge whether it is possible to complete all the courses? If so, return true; Otherwise, return false

Leetcode-cn.com/problems/co…

Example 1:

Input: numCourses = 2, resident = [[1,0]] output: true Before you can study course 1, you need to complete course 0. It’s possible.

Example 2:

Input: numCourses = 2, prerequisites = [[1,0],[0,1]] You need to complete Course 0 before taking course 1; And you should also complete course 1 before taking course 0. It’s impossible.

Tip:

1 <= numCourses <= 105 0 <= prerequisites.length <= 5000 prerequisites[i].length == 2 0 <= ai, Bi < numCourses Prerequisites [I] all course pairs are different

Java solution

Ideas:

  • Preliminary thinking, this kind of related data is similar to the structure of the linked list. If the linked list has rings, the data will be locked to each other and cannot be learned

    • Bidirectional linked list: the former node is the pre-learning course, and the latter node is the follow-up learning course. No former node can be used as the starting point of the learning course
    • Learning quantity: can be returned by starting point traversal count

  • Since no data structure is provided to solve the problem, hashMap is first used to record the corresponding relationship

    public static boolean canFinish(int numCourses, int[][] prerequisites) {
    if (prerequisites == null||prerequisites.length==0) {
        return true;
    }
    HashMap<Integer, List<Integer>> map = new HashMap<>();// Make a note of the b lessons you need to learn first
    HashMap<Integer, List<Integer>> map2 = new HashMap<>();// Make a note of the class A you have learned and the class B you can learn
    for (int[] prerequisite : prerequisites) {
        List<Integer> list = map.getOrDefault(prerequisite[0].new ArrayList<>());
        list.add(prerequisite[1]);
        List<Integer> list1 = map.getOrDefault(prerequisite[1].new ArrayList<>());
        map.put(prerequisite[0], list);
        map.put(prerequisite[1], list1);

        List<Integer> integers = map2.getOrDefault(prerequisite[1].new ArrayList<>());
        integers.add(prerequisite[0]);
        map2.put(prerequisite[1],integers);
    }
    List<Integer> start = new ArrayList<>();
    for (Map.Entry<Integer, List<Integer>> entry : map.entrySet()) {
        if (entry.getValue()==null||entry.getValue().size()==0) { start.add(entry.getKey()); }}int count = numCourses;
    for (Integer integer : start) {
        count--;
        int unLearn = learnFinish(map2, integer, count);
        if (unLearn<=0) {
            return true;
        }
        count = unLearn;
    }
    return count<=0;
}
public static int learnFinish(HashMap<Integer, List<Integer>> map,int index,int count){
    List<Integer> integers = map.getOrDefault(index,new ArrayList<>());
    count-=integers.size();
    for (Integer i : integers) {
        count -= learnFinish(map, i, count);
    }
    return count;
}
Copy the code

  • The number of courses here is irrelevant to the result. What is required here is whether the course can be completed. The brain is big

  • Refer to the official solution: topological sort + depth-first search + backtracking

    • Use arrays to record the search status, and use stack record backtracking to complete the node traversal
package sj.shimmer.algorithm.m4_2021;

import java.util.ArrayList;
import java.util.List;

/** * Created by SJ on 2021/4/19. */

class D82 {
    public static void main(String[] args) {
        System.out.println(canFinish(2.new int[] [] {{1.0},
                {2.1}})); System.out.println(canFinish(20.new int[] [] {{0.10},
                {3.18},
                {5.5},
                {6.11},
                {11.14},
                {13.1},
                {15.1},
                {17.4}})); System.out.println(canFinish(1.new int[] [] {})); }static List<List<Integer>> edges;
    static int[] visited;//0 not searched, 1 searching (loop, cannot complete), 2 complete
    static boolean valid = true;

    public static boolean canFinish(int numCourses, int[][] prerequisites) {
        edges = new ArrayList<List<Integer>>();
        for (int i = 0; i < numCourses; ++i) {
            edges.add(new ArrayList<Integer>());
        }
        visited = new int[numCourses];
        for (int[] info : prerequisites) {
            edges.get(info[1]).add(info[0]);// Record all available lessons learned,
        }
        for (int i = 0; i < numCourses && valid; ++i) {
            if (visited[i] == 0) {
                dfs(i);// Start a deep search}}return valid;
    }

    public static void dfs(int u) {
        visited[u] = 1;
        for (int v: edges.get(u)) {
            if (visited[v] == 0) {
                dfs(v);
                if(! valid) {return; }}else if (visited[v] == 1) {
                valid = false;
                return;
            }
        }
        visited[u] = 2; }}Copy the code

The official solution

Leetcode-cn.com/problems/co…

  1. Depth-first search

    As above

    • Time complexity:O(n+m)
  • Space complexity:O(n+m)
  1. Breadth-first search: reverse operations from above