207. Curriculum

Title Source: LeetCode https://leetcode-cn.com/problems/course-schedule

subject

You must take numCourse courses this semester, marked as 0 to numCourse-1.

Some prerequisite courses are required before taking some courses. For example, to learn course 0, you need to complete course 1 first. We use a match to represent them: [0,1]

Given the total number of courses and their prerequisites, can you judge whether it is possible to complete all courses?

Example 1:

input: 2, [[1,0]]
output: true
 explain: There are two courses in total. You need to complete course 0 before learning course 1. So it's possible.

Example 2:

input: 2, [[1,0],[0,1]]
output: false
 explain: There are two courses in total. You need to complete the course before you study the course 1​Course 0; You should also complete course 1 before studying course 0. It's impossible.

Tips:

1. The prerequisite for entering is the graph represented by the edge list, not the adjacency matrix. For details, see Representation of Graphs.
2. You can assume that there are no duplicate edges in the input prerequisites.
3. 1 <= numCourses <= 10^5

Problem solving ideas

Idea: topology sorting (BFS, DFS)

In fact, this is a classic [topological sorting] problem.

First, let's examine the question first. Combined with example 1 and example 2, we can see that the question actually asks whether the graph (i.e. curriculum) represented by a given input prerequisite is a directed acyclic graph. In other words, after determining the preconditions, the graph cannot have a ring, otherwise it will not hold.

Directed acyclic graph (DAG): a directed graph is a directed acyclic graph if it starts from any vertex and cannot return to that point through several edges.

Directed acyclic graph, details can be understood from the entrance below
https://en.wikipedia.org/wiki/Directed_acyclic_graph (Wikipedia: directed acyclic graph)
https://baike.baidu.com/item/%E6%9C%89%E5%90%91%E6%97%A0%E7%8E%AF%E5%9B%BE/10972513?fr=aladdin (Baidu Encyclopedia: directed acyclic graph)

Then, when it is required whether the curriculum arrangement graph is a directed acyclic graph, we use topological sorting to judge. Topological sorting: sort all vertices of the graph into a linear sequence, so that any directed edge uv and u in the graph appear in front of v in the linear sequence.

Topology sorting. The details can be understood from the entry below
https://en.wikipedia.org/wiki/Topological_sorting (Wikipedia: topological sorting)
https://baike.baidu.com/item/%E6%8B%93%E6%89%91%E6%8E%92%E5%BA%8F/5223807?fr=aladdin (Baidu Encyclopedia: topological sorting)

It is explained in the prompt in the title that the entered prerequisites are represented by the edge list. Here, we want to convert this into an adjacency table.

Adjacency table. The details can be understood from the entry below
https://en.wikipedia.org/wiki/Adjacency_list (Wikipedia: adjacency table)
https://baike.baidu.com/item/%E9%82%BB%E6%8E%A5%E8%A1%A8/9796152?fr=aladdin (Baidu Encyclopedia: adjacency table)

Breadth first (BFS)

Firstly, the preconditions represented by the edge list are transformed to obtain the adjacency table. Then, the penetration of each node in the graph is counted and stored in a list. (when the penetration is 0, it means that the point is not the end of any edge, that is, the point is the starting point of all connected edges)

Here, the auxiliary queue is defined to store all nodes with a penetration of 0 into the queue for subsequent processing.

Start the search and dequeue the nodes in the queue:

• Reduce the penetration of adjacent nodes of the current node by 1;
• When the penetration of adjacent nodes is 0, they are queued.

When the nodes in the queue are out of the queue, reduce the total number of courses by 1:

• If the course graph is a directed acyclic graph, if the topological sorting is completed, all nodes will join and leave the queue;
• If there is a ring in the course map, there must be a case where the node penetration is not 0;
• In other words, when all nodes join and leave the team and the total amount of courses is 0, it can prove whether the course map is a directed acyclic graph.

See [code implementation # breadth first search] for specific code

Depth first search (DFS)

Let's first look at the idea of using depth first search to judge whether the graph has rings.

Here, we mark the status of each node with an auxiliary list (of course, we can also consider using stack):

• Not marked, so that the status is 0 at this time;
• Temporary mark, so that the status is 1 at this time;
• Permanently mark, so that the status is - 1 at this time.

Start the depth first search for each node. When there is a ring, return False. The execution process is as follows:

• When the node status is - 1, it indicates that it has been permanently marked. At this time, the search has been completed. Repeated search is not allowed, and True is returned directly;
• When the node status is 1, it indicates a temporary flag, that is, the node has been searched again in this deep search. If there is a ring in the graph, it will directly return False;
• When the status is 0, first mark the node temporarily (make the status 1), and then continue the search at this point until the termination condition is encountered.
• When the node search is completed and no closed loop is found, remove the temporary mark and permanently mark the node (make the status - 1)

Returns True if there is no ring after all nodes are searched.

See [code implementation # depth first search] for specific code

code implementation

# Breadth first search
class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        from collections import deque

        # Convert the prerequisites represented by the edge list to an adjacency table
        adjacency = [[] for _ in range(numCourses)]
        # Define the penetration of each node in the list statistics chart
        indegree = [0] * numCourses

        for info in prerequisites:
            adjacency[info[1]].append(info[0])
            indegree[info[0]] += 1
        
        queue = deque()

        # Queue nodes with a degree of 0
        for i in range(len(indegree)):
            if not indegree[i]:
                queue.append(i)
        # Start search
        while queue:
            u = queue.popleft()
            numCourses -= 1
            # Search adjacent nodes
            for v in adjacency[u]:
                # Reduce the penetration of adjacent nodes by 1
                indegree[v] -= 1
                # If the score is 0, join the team
                if indegree[v] == 0:
                    queue.append(v)

        return numCourses == 0

# Depth first search
class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        def dfs(adjacency, sign, i):
            if sign[i] == -1:
                return True
            if sign[i] == 1:
                return False
            # Start the search and mark temporarily first
            sign[i] = 1
            # Search down with this node
            for j in adjacency[i]:
                if not dfs(adjacency, sign, j):
                    return False
            sign[i] = -1
            return True

        # Defines the auxiliary list tag status, which is initialized to 0, indicating that it is not marked
        sign = [0] * numCourses
        # Convert the prerequisites represented by the edge list to an adjacency table
        adjacency = [[] for _ in range(numCourses)]
        for info in  prerequisites:
            adjacency[info[1]].append(info[0])
        
        # Start deep search
        for i in range(numCourses):
            if not dfs(adjacency, sign, i):
                return False
        return True

Implementation results

Welcome to pay attention

Official account[ Collection of books]