LeetCode Course Schedule

Description

There are a total of n courses you have to take, labeled from 0 to n - 1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

For example:

2, [[1,0]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.

2, [[1,0],[0,1]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

The original problem is here.

The original code is here.

My Solution

I solve this problem in C++, as below:

/*
*Course Schedule 
*Author: shuaijiang
*Email: zhaoshuaijiang8@gmail.com
*/
#include<iostream>
#include<map>
#include<vector>
#include<stdlib.h>
using namespace std;

class Solution {
public:
    map<int, vector<int> > myMap;
    map<int, vector<int> >::iterator iter;
    bool canFinish(int numCourses, vector<pair<int, int> >& prerequisites) {
        int len = prerequisites.size();
        vector<int> visit(numCourses, 0);   

        
        for(int i=0;i<len;i++){
            int num1 = prerequisites[i].first;
            int num2 = prerequisites[i].second;
            if(myMap.find(num1) == myMap.end()){
                vector<int> vec(1,num2);
                myMap[num1] = vec;
            }
            else{
                (myMap[num1]).push_back(num2);
            }
        }
        for(iter = myMap.begin();iter != myMap.end(); iter++){
            vector<int> nums = iter->second;
            int begin = iter->first;
            visit[begin] = -1;
            for(int j=0;j<nums.size();j++){
                if(dfs(nums[j], visit))
                    return false;
            }
            visit[begin] = 1;
        }
        return true;
    }
    bool dfs(int num, vector<int> &visit) {
        cout<<"num="<<num<<endl;
        if(visit[num] == -1)
            return true;
        if(visit[num] == 1)
            return false;
            
        visit[num] = -1;
        vector<int> vec;
        if(myMap.find(num) != myMap.end()) 
            vec = myMap[num];
        
        for(int i=0;i<vec.size();i++){
            if(dfs(vec[i], visit))
                return true;
        }
        visit[num] = 1;
        return false;
    }
};

int main(){
    Solution s;
    pair<int, int> n1(0,1);
    pair<int, int> n2(3,1);
    pair<int, int> n3(1,3);
    pair<int, int> n4(3,2);
    
    vector<pair<int,int> > vec;
    vec.push_back(n1);
    vec.push_back(n2);
    vec.push_back(n3);
    vec.push_back(n4);
    bool res = s.canFinish(4, vec);
    cout<<"res="<<res<<endl;
    system("pause");
    return 0;
}

Note

To solve the problem, depth-first search was used. The visited path is recorded, to reduce the used time, label the unvisited one to 0, label the visited one to -1, label the visited and without cycle ont to 1.