Wednesday, May 13, 2015

LeetCode [210] Course Schedule II

 210. Course Schedule II

Medium

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

Some courses may have prerequisites, for example, if prerequisites[i] = [ai, bi] this means you must take the course bi before the course ai.

Given the total number of courses numCourses and a list of the prerequisite pairs, return the ordering of courses you should take to finish all courses.

If there are many valid answers, return any of them. If it is impossible to finish all courses, return an empty array.

 

Example 1:

Input: numCourses = 2, prerequisites = [[1,0]]
Output: [0,1]
Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1].

Example 2:

Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: [0,2,1,3]
Explanation: There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0.
So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3].

Example 3:

Input: numCourses = 1, prerequisites = []
Output: [0]

 

Constraints:

  • 1 <= numCourses <= 2000
  • 0 <= prerequisites.length <= numCourses * (numCourses - 1)
  • prerequisites[i].length == 2
  • 0 <= ai, bi < numCourses
  • ai != bi
  • All the pairs [ai, bi] are distinct.
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
//C++: method1 740ms label the courses along the recursion
class Solution {
public:
    vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
        vector<int> label(numCourses), ret;
        bool visited[2000] = {false};
        int cur_label = numCourses;
        for(int i=0; i<numCourses; ++i){
            if(!visited[i]) dfs(i, prerequisites, visited, label, cur_label, ret);
        }
        for(auto p:prerequisites){
            if(label[p.first]<label[p.second]){
                return vector<int>();
            }
        }
        reverse(ret.begin(), ret.end());
        return ret;
    }
    
    void dfs(int course, vector<pair<int, int>>& prerequisites, bool *visited, vector<int> &label, int &cur_label, vector<int> &ret){
        visited[course] = true;
        for(auto p:prerequisites){
            if(course==p.second && !visited[p.first]){
                dfs(p.first, prerequisites, visited, label, cur_label, ret);
            }
        }
        label[course] = --cur_label;
        ret.push_back(course);
    }    
};

//C++: method2 524ms standard dfs method using a stack
#define NC 2000
class Solution {
public:
    vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
        bool preqs[NC][NC] = {false};
        for(auto p:prerequisites) preqs[p.second][p.first] = true;
        bool visited[NC] = {false};
        bool path[NC] = {false};

        stack<int> stk;
        vector<int> ret;
        for(int i=0; i<numCourses; ++i){
            if(!visited[i]){
                path[i] = true;
                if(hasCycle(numCourses, i, stk, preqs, visited, path)) return ret;
                path[i] = false;
            }
        }

        while(!stk.empty()){
            ret.push_back(stk.top());
            stk.pop();
        }
        return ret;

    }
    
    bool hasCycle(int N, int node, stack<int> &stk, bool preqs[][NC], bool *visited, bool *path){
        visited[node] = true;
        for(int i=0; i<N; ++i){
            if(preqs[node][i]){
                if(path[i]) return true;
                path[i] = true;
                if(!visited[i]) if(hasCycle(N, i, stk, preqs, visited, path)) return true;
                path[i] = false;
            }
        }
        stk.push(node);
        return false;
    }
};

//C++: method3 620ms  dfs method without a stack
class Solution {
public:
    vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
        vector<int> order;
        bool visited[numCourses];
        memset(visited, false, numCourses*sizeof(bool));
        bool path[numCourses];
        memset(path, false, numCourses*sizeof(bool));

        for(int i=0; i<numCourses; ++i){
            path[i] = true;
            if(!visited[i] && hasCycle(numCourses, prerequisites, i, visited, path, order)){
                order.clear();
                return order;
            }
            path[i] = false;
        }
        reverse(order.begin(), order.end());
        return order;
    }
    bool hasCycle(int numCourses, vector<pair<int, int>>& prerequisites, int curNode, bool *visited, bool *path, vector<int> &order){
        visited[curNode] = true;
        for(auto p:prerequisites){
            if(p.second==curNode){
                if(path[p.first]) return true;
                if(!visited[p.first]){
                    path[p.first] = true;
                    if(hasCycle(numCourses, prerequisites, p.first, visited, path, order))
                        return true;
                    path[p.first] = false;
                }
            }
        }
        order.push_back(curNode);
        return false;
    }
};

//Java
class Solution {
    Set<Integer> path, visited;
    Map<Integer, Set<Integer>> preqs;
    List<Integer> schedule;
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        path = new HashSet<>();
        visited = new HashSet<>();
        preqs = new HashMap<>();
        schedule = new ArrayList<>();
        for(int[] p : prerequisites){
            preqs.computeIfAbsent(p[0], k -> new HashSet<Integer>()).add(p[1]);
        }

        for(int c = 0; c<numCourses; ++c){
            path.add(c);
            if(!visited.contains(c) && hasCycle(c))
                return new int[0];
            path.remove(c);
        }

        int[] ret = new int[schedule.size()];
        for(int i=0; i<schedule.size(); ++i) ret[i] = schedule.get(i);
        return ret;
    }

    boolean hasCycle(int course){
        visited.add(course);
        if(preqs.containsKey(course)){
            for(int p : preqs.get(course)){
                if(path.contains(p)) return true;
                path.add(p);
                if(!visited.contains(p) && hasCycle(p)) return true;
                path.remove(p);
            }
        }
        schedule.add(course);
        return false;
    }
}
Posted by at
Labels:

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)