O(N^2) c++, fairly straightforward


  • 0
    O

    For each course, check what prerequisites are required, and if they have been satisfied. If all prereqs satisfied, take course, otherwise continue searching. Stop when you can find no more courses to take.

    This is O(N^2), I feel a better solution (O(NlogN)) might be possible using some form of pivot, but can't say for certain and couldn't figure this out (hard because no strict ordering of courses).

    class Solution {
    public:
        bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
            bool taken[numCourses];
            for(int i=0;i<numCourses;i++) taken[i] = 0;
            vector<vector<int>> prereqs(numCourses);
            for(int i=0;i<prerequisites.size();i++){
                prereqs[prerequisites[i][0]].push_back(prerequisites[i][1]);
            }
            int last_check = 0;
            int check = 0;
            while(1){
                if (!taken[check]){
                    bool take = 1;
                    for(int i=0;i<prereqs[check].size() && take;i++) if (!taken[prereqs[check][i]]) take = 0;
                    if (take) {taken[check]=1; last_check = check;}
                }
                check++;
                check%=numCourses;
                if (check==last_check) break;
            }
            for(int i=0;i<numCourses;i++) if (!taken[i]) return 0;
            return 1;
        }
    };

  • 0
    J

    do not write your codes like this.
    it's quite uncomforting to write several sentences within one line;


Log in to reply
 

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