lc207-Course Schedule

發表於   |   分類於   |   0 comments   |   
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
class graph {
    vector<unordered_set<int>> adj;
    int n;
    vector<int> temp_visited;
    vector<int> perm_visited;
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);
        }
    }
    bool containsCycle() {
        for (int i = 0; i < n; i++)
            if (!perm_visited[i])
                if (dfs(i)) return true;
        return false;
    }
    bool dfs(int cur) {
        if (perm_visited[cur]) return false;
        temp_visited[cur] = 1;
        for (int next:adj[cur]) {
            if (temp_visited[next]) return true;
            if (dfs(next)) return true;
        }
        temp_visited[cur] = 0;
        perm_visited[cur] = 1;
        return false;
    }
};
class Solution {
public:
    bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
        graph g(numCourses, prerequisites);
        return !(g.containsCycle());
    }
};