1. Topic description

Now you have a total of n classes you need to take, zero to n minus one.

Some prerequisite courses are required before you can take certain courses. For example, to take course 0, you need to complete course 1 first. We represent them with a match: [0,1]

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

Example 1:

Input: 2, [[1,0]] output: true explanation: there are 2 courses. Before you can study course 1, you need to complete course 0. So it’s possible.

Example 2:

Input: 2, [[1,0],[0,1]] output: false explanation: there are 2 courses in total. You need to complete Course 0 before taking course 1; And you should also complete course 1 before taking course 0. It’s impossible.

2

This is a graph problem, this aspect of the algorithm did not have much contact, only BFS and DFS have some understanding. First of all, the input of this problem brought me some difficulty, that is, how to express this graph is more convenient? It’s not very convenient to search directly on the basis of this existing input. The most commonly used graph representation methods are adjacency list and adjacency matrix. This topic is more suitable for adjacency list, because DFS or BFS can directly traverse the adjacent nodes. And of course the adjacency matrix should also work. Node representation is as follows:

struct Node{
    int id;
    vector<Node*> neighbors;
    Node(int x): id(x) {}
    
};
Copy the code

Whether the course can be completed depends on whether there are rings in the directed graph. So this is a problem that can be solved with DFS. DFS is used to search all the nodes in the graph, and if a point search is found later on a search path, then there is a loop and the lesson cannot be completed. So how should the specific process to search? First, a Visited array is used to represent the access state of nodes. Then, nodes are taken from the graph in sequence as the starting point of search. Search along the adjacent points of this point, set the points found on this search path to 0, until the point found in the state of 0 is searched again, it indicates that there is a ring, return false; If no nodes are searched and no rings are found, the change point is set to 1, indicating that all paths from this point have no rings. It is easy to have a question here. Usually, visited of DFS only has bool type of two states. Why do we need three states here? This is mainly because there is a status that needs to be recorded in addition to being searched and not being received. I’m searching for two states, one is I’m searching for this path, I’m not done yet, I don’t know if there’s a loop, and I’m in a state of zero. The other state, where all the paths from this node have been searched, there are no loops, and we don’t have to go to this point anymore, is state 1. The point that has never been entered is negative 1. So the ring will only appear if the state is 0 and is searched again. You don’t have to enter a point that’s already set to 1, you can only enter a point that’s in the -1 state.

3. Code implementation

In the code template corresponding to DFS, enter DFS from a point in the graph, first set the state to 0, and then iterate over the adjacent nodes to get the point with the state of -1 to further DFS. If the status of the adjacent nodes is 1, skip it; if it is 0, the loop returns false. After all loops are loopless, the current node can be set to 1.

class Solution {
public:
    struct Node{
        int id;
        vector<Node*> neighbors;
        Node(int x): id(x) {}
        
    };
    
    bool DFS(Node* p, vector<int>& visited){
        visited[p->id] = 0;
        for(auto pNext : p->neighbors){
            if(visited[pNext->id] == - 1) {if(DFS(pNext, visited) == false)
                    return false;
            }
            else if(visited[pNext->id] == 0) {return false;
            }
        }
        visited[p->id] = 1;
        return true;
    }
    
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        if(numCourses == 0)
            return false;
        // Visited refers to the state of the node.-1 means that it has never been searched, 0 means that it is on the searching path, and 1 means that it has searched the point that is confirmed to be acyclic
        vector<int> visited(numCourses, - 1);
        // Construct the points in the graph
        vector<Node*> graph(numCourses);
        for(int i = 0; i < numCourses; i++){
            Node* tmp = new Node(i);
            graph[i] = tmp;
            
        }
        // Add the adjacent edge to the neighbors of the node
        for(auto pair : prerequisites){
            graph[pair[1]]->neighbors.push_back(graph[pair[0]]);
        }
        // Start the DFS search
        for(int i = 0; i < numCourses; i++){
            if(visited[i] == - 1) {if(DFS(graph[i], visited) == false)
                    return false; }}return true; }};Copy the code