lc210-Course Schedule II

發表於   |   分類於   |   0 comments   |  

updated Dec 13:

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
class graph {
    vector<unordered_set<int>> adj;
    int n;
    vector<int> temp_visited;
    vector<int> perm_visited;
    vector<int> sort_result;
public:
    void add_edge(int u, int v) {
        adj[u].insert(v);
    }
    graph(int V, vector<pair<int, int>>& prerequisites):perm_visited(V, 0), temp_visited(V, 0), adj(V, unordered_set<int>()) {
        n = V;
        for (auto p:prerequisites) {
            add_edge(p.second, p.first);
        }
    }
    vector<int> topologicalSort() {
        for (int i = 0; i < n; i++)
            if (!perm_visited[i]) {
                dfs(i);
                if (sort_result.empty()) return sort_result;
            }
        reverse(sort_result.begin(), sort_result.end());
        return sort_result;
    }
    void dfs(int cur) {
        if (perm_visited[cur]) return;
        temp_visited[cur] = 1;
        for (int next:adj[cur]) {
            if (temp_visited[next]) {
                sort_result = vector<int>();
                return;
            }
            dfs(next);
            if (sort_result.empty()) return;
        }
        temp_visited[cur] = 0;
        perm_visited[cur] = 1;
        sort_result.push_back(cur);
        return;
    }
};
class Solution {
public:
    vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
        graph g(numCourses, prerequisites);
        return g.topologicalSort();
    }
};
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(object):
    def findOrder(self, numCourses, prerequisites):
        """
        :type numCourses: int
        :type prerequisites: List[List[int]]
        :rtype: List[int]
        """
        def dfs(root):
            # print "root:",root
            marked = [0] * numCourses
            stack = []
            stack.append(root)
            while stack:
                s = stack[-1]
                if visited[s]:
                    stack.pop()
                    if marked[s]:
                        res.append(s)
                    marked[s] = 0
                else:  
                    visited[s] = 1
                    marked[s] = 1
                    if len(pre[s]) == 0:
                        stack.pop()
                        marked[s] = 0
                        res.append(s)
                        continue
                    for x in pre[s]:
                        if x in stack and marked[x] == 1:
                            return 0
                        stack.append(x)
            return 1
        roots = range(numCourses)
        pre = [[]]*numCourses
        for i in range(numCourses):
            pre[i] = []
        visited = [0]*numCourses
        res = []
        for i in range(len(prerequisites)):
            # print "iter",i
            after = prerequisites[i][0]
            prev = prerequisites[i][1]
            if prev in roots:
                roots.remove(prev)
            pre[after].append(prev)
        for root in roots:
            if not dfs(root):
                return []
        if 0 in visited:
            return []
        return res