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.