My simple solution using Topological sort


  • 0
    M
    class Solution {
    public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
    	if (numCourses <= 1)
    		return true;
    
    	vector<int>inner = { 0 };
    	vector<vector<int> >course(numCourses, inner);
    	for (auto i : prerequisites){
    		course[i[1]].push_back(i[0]);
    		course[i[0]][0]++;
    	}
    	int flag = 0;
    	while (true){
    		for (int i=0;i<numCourses;i++){
    			if (course[i][0] == 0){
    				for (auto iter = course[i].begin() + 1; iter != course[i].end();iter++){
    					course[*iter][0]--;
    				}
    				course[i][0] = -1;
    				flag = 1;
    				break;
    			}
    		}
    		if (flag == 0){
    			for (auto i : course){
    				if (i[0] != -1){
    					return false;
    				}
    			}
    			return true;
    		}
    		else{
    			flag = 0;
    		}
    	}
    }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.