1, Topic analysis

(1) The problem can be abstracted as detecting whether a directed graph has a ring. If yes, return False; If not, return True.
(2) For a directed graph, we can delete nodes with zero penetration one by one. For each deleted node, the connected directed line segment will also be deleted (i.e. the penetration of this point as the preamble course is - 1). It is easy to analyze that this process will not destroy the ring in the graph (if it exists, the penetration of each point in the ring is not zero, so it cannot be deleted.)
Therefore, the process is iterated until there is no point with zero penetration. At this time, if the graph still exists (there are still points), the existence of a ring can be judged.
(3) Now the above principle:
On the representation of directed graph: since the inputs given by the topic are int data, two arrays and one-dimensional array can be directly used to store the penetration of the course represented by each numbered course, and its index is the course number; The other is a two-dimensional array, which is used to store the subsequent courses of the course represented by the index number.
Starting from any point with 0 degree, traverse the whole graph and delete the points with 0 degree in turn. BFS algorithm or DFS algorithm can be used for traversal.

2, Problem solution and code

2.1

Here, BFS algorithm is used for reference This is a great answer , it's written very well. The initialization variable stunned me. For the first time, I was confused from beginning to end. The next day I went to watch the BFS and DFS algorithm of the day (about this wall crack, I recommend the teaching video of the main 'lantern on the first moon' of the UP of station B, link) Offer . )， From principle to implementation, the third day I can understand and make some small changes. For example, the answer traversal uses the deque bidirectional queue in the collections library. I'm not too familiar with it. After searching, I feel that this problem can be realized by using the ordinary queue learned the day before. So when you reproduce, you directly use an ordinary array.
The detailed explanation code is as follows:

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        #### Initialize the required variables
        indegress = [0 for _ in range(numCourses)] # One dimensional array, stored in degrees
        adjacency = [[]for _ in range(numCourses)] # Two dimensional array for subsequent courses
        queue = []  # Queue used to traverse
        nums = numCourses # Record the remaining nodes in the diagram

        ### Represent the graph
        for cour,pre in prerequisites:
            indegress[cour] += 1
            adjacency[pre].append(cour)
        
        ### Put the first batch of vertexes whoesindegrees is 0 into the queue
        for i in range(len(indegress)):
            if indegress[i] == 0: 
                queue.append(i)
        ### Traverse the entire graph, removing points with 0 indegree
        while queue:
            ver = queue.pop(0)  # It doesn't matter here whether pop(0) or pop(). The former is BFS and the latter is DFS algorithm.
            nums -= 1    # Traverse a node and reduce the number of nodes by one
            for i in adjacency[ver]:
                indegress[i] -= 1  # For the points with 0 penetration traversed and deleted, delete them at the same time
                if not indegress[i] : queue.append(i)
        ### Returns True if the number of remaining vertexes is 0
        return not nums

In addition, if the input course information is not represented by int data, but by str, indepress and adjacency can choose dictionary data to construct, which are also one-dimensional and two-dimensional respectively.