Tuesday, May 12, 2015

LeetCode [207] Course Schedule

207. Course Schedule
Medium
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?
Example 1:
Input: 2, [[1,0]] 
Output: true
Explanation: There are a total of 2 courses to take. 
             To take course 1 you should have finished course 0. So it is possible.
Example 2:
Input: 2, [[1,0],[0,1]]
Output: false
Explanation: 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.
Note:
  1. The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
  2. You may assume that there are no duplicate edges in the input prerequisites.
 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
class Solution {
public:
    void dfs(int index, int & current_label, vector<pair<int, int>>& prerequisites, int *visited, int *label, int numCourses){
        visited[index] = 1;
        for(vector<pair<int, int>>::iterator it=prerequisites.begin(); it!=prerequisites.end(); it++){
            if(it->first==index){
                if(visited[it->second]==0)
                    dfs(it->second, current_label, prerequisites, visited, label, numCourses);
            }
        }
        label[index] = current_label--;
    }

    bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
        int visited[2000] = {0};
        int label[numCourses];
        int current_label = numCourses-1;
        for(int i=0; i<numCourses; ++i) {
            if(visited[i]==0){
                dfs(i, current_label, prerequisites, visited, label, numCourses);
            }
        }
        for(vector<pair<int, int>>::iterator it=prerequisites.begin(); it!=prerequisites.end(); it++){
            if(label[it->first]>label[it->second]) return false;
        }
        return true;
    }
};

 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
enum class Color{white, gray, black};

class Solution {
    vector<Color> colors;
public:
    bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
        colors.resize(numCourses, Color::white);
        for(int i=0; i<numCourses; ++i){
            if(colors[i]==Color::white){
                if(hasCycle(i, prerequisites)) return false;
            }
        }
        return true;
    }

    bool hasCycle(int course, vector<pair<int, int>>& prerequisites){
        colors[course] = Color::gray;
        for(auto p:prerequisites){
            if(p.second==course){
                if(colors[p.first]==Color::gray) return true;
                if(colors[p.first]==Color::white){
                    if(hasCycle(p.first, prerequisites)) return true;
                }
            }
        }
        colors[course] = Color::black;
        return false;
    }
};

 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
class Solution {
public:
    bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
        int current_label = numCourses, i = 0;
        stack<int> stk;
        bool visited[numCourses];
        int labels[numCourses];
        memset(visited, false, numCourses*sizeof(bool));
        
        while(i<numcourses || !stk.empty()){
            if(stk.empty()){
                while(i<numCourses && visited[i]) i++;
                if(i<numCourses) stk.push(i);
            }else{
                int u = stk.top();
                visited[u] = true;
                bool hasChild = false;
                for(auto p:prerequisites){
                    if(p.first==u){
                        int v = p.second;
                        if(!visited[v]){ stk.push(v); hasChild = true;}
                    }
                }
                if(!hasChild){ 
                    labels[u] = current_label--; 
                    stk.pop();
                }
            }
        }
        
        for(auto p:prerequisites){
            int u = p.first, v = p.second;
            if(labels[u]>labels[v]) return false;
        }
        return true;
    }
};

 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
class Solution {
public:

    bool isSource(int index, vector<pair<int, int>>& prerequisites, int N, int *deletedEdge, int nE){
        int s[N];
        memset(s,0,N*sizeof(int));
        for(int i=0; i<nE; ++i){
            if(deletedEdge[i]==0) s[prerequisites[i].second] = 1;//it->second is not source
        }
        return s[index]==0;
    }

    queue<int> getSources(vector<pair<int, int>>& prerequisites, int N, int *deletedEdge, int nE){
        queue<int> sources;
        int s[N];
        memset(s,0,N*sizeof(int));
        for(int i=0; i<nE; ++i){
            if(deletedEdge[i]==0) s[prerequisites[i].second] = 1;//it->second is not source
        }
        for(int i=0; i<N; ++i){
            if(s[i]==0) sources.push(i);
        }
        return sources;
    }



    bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
        int nE = prerequisites.size();
        int deletedEdge[nE];
        memset(deletedEdge,0,nE*sizeof(int));
        queue<int> sources = getSources(prerequisites, numCourses, deletedEdge, nE);
        int delE = 0;
        while(!sources.empty()){
            int n = sources.front();
            sources.pop();
            for(int i=0; i<nE; ++i){
                if(deletedEdge[i]==0 && prerequisites[i].first==n){
                    int m = prerequisites[i].second;
                    deletedEdge[i] = 1;
                    delE++;
                    if(isSource(m, prerequisites, numCourses, deletedEdge, nE)){
                        sources.push(m);
                    }
                }
            }
        }
        return delE==nE;
    }

};

 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
class Solution {
public:
    bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
        vector<unordered_set<int>> prs(numCourses);
        for(auto p:prerequisites){
            prs[p.second].insert(p.first);
        }

        unordered_set<int> visited;
        for(int i=0; i<numCourses; i++){
            unordered_set<int> path;
            path.insert(i);
            if(visited.count(i)==0 && hasCycle(numCourses, prs, path, i, visited)) return false;
        }
        return true;
    }
    bool hasCycle(int numCourses, vector<unordered_set<int>> &prs, unordered_set<int> &path, int node, unordered_set<int> &visited){
        visited.insert(node);
        for(int i:prs[node]){
            if(path.count(i)>0) return true;
            path.insert(i);
            if(visited.count(i)==0 && hasCycle(numCourses, prs, path, i, visited)) return true;
            path.erase(i);
        }
        return false;
    }
};


 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
class Solution {
    Set<Integer> visited;   
    Set<Integer> path;
    Map<Integer, Set<Integer>> preq;
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        visited = new HashSet<>();
        path = new HashSet<>();
        preq = new HashMap<>();
        for(int[] p : prerequisites){
           preq.computeIfAbsent(p[0], k -> new HashSet<>()).add(p[1]);
        }

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

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

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)