207.Course Schedule I & II

课程表规划问题,一般来说主要考虑是否存在环。

207. Course Schedule

题目

207. Course Schedule
是否存在环

1
2
Input: 2, [[1,0],[0,1]]
Output: false

思路1

我自己想了一个思路,就是从入度着手。

1、把所有入度为0的节点找出来,从这些节点开始。(为什么不用别的节点?没用啊,既然入度不是0,那么这个节点肯定包含在另外一个入度是0节点构造的树中)。
2、然后把这几个入度是0的节点删除
3、循环1->2,直到找不到新的入度为0的节点,这个时候,如果所有节点都被访问过了,那么无环。否则有环 /如果有环的话,每个节点都入度出度为1。

代码1

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 canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {

vector<unordered_set<int>> adj_out(numCourses);
vector<unordered_set<int>> adj_in(numCourses);

for (pair<int, int> p : prerequisites) {
adj_out[p.first].insert(p.second);
adj_in[p.second].insert(p.first);
}

// 把根找出来
vector<int> root;
for (int i = 0; i < numCourses; i++) {
if (adj_in[i].size()==0) {
root.push_back(i);
}
}
// 直接就是个圆
if (root.size() == 0)
return false;

stack<int> st;
vector<int> visit;

while (visit.size() != numCourses) {
if (root.size() == 0)
return false;
for (int i : root) {
visit.push_back(i);
if (adj_out[i].size() == 0)
continue;

for (int j : adj_out[i]) {
adj_in[j].erase(i);
}
}
// 更新 root
root.clear();
for (int i = 0; i < numCourses; i++) {
if (adj_in[i].size() == 0 && find(visit.begin(),visit.end(),i)==visit.end()) {
root.push_back(i);
}
}
}

return true;
}
};

感觉不复杂啊,只不过有些操作 cpp 实现起来比较蛋疼,不过速度非常慢,貌似需要1400ms

思考

上边我描述的比较民科,如果正规的描述,本问题就是检查是不是有环,使用拓扑排序+BFS或者DFS有助于解决此问题。

  • BFS版

    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
    class Solution {
    public:
    bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
    vector<unordered_set<int>> graph = make_graph(numCourses, prerequisites);
    vector<int> degrees = compute_indegree(graph);
    for (int i = 0; i < numCourses; i++) {
    int j = 0;
    for (; j < numCourses; j++)
    if (!degrees[j]) break;
    if (j == numCourses) return false;
    degrees[j] = -1;
    for (int neigh : graph[j])
    degrees[neigh]--;
    }
    return true;
    }
    private:
    vector<unordered_set<int>> make_graph(int numCourses, vector<pair<int, int>>& prerequisites) {
    vector<unordered_set<int>> graph(numCourses);
    for (auto pre : prerequisites)
    graph[pre.second].insert(pre.first);
    return graph;
    }
    vector<int> compute_indegree(vector<unordered_set<int>>& graph) {
    vector<int> degrees(graph.size(), 0);
    for (auto neighbors : graph)
    for (int neigh : neighbors)
    degrees[neigh]++;
    return degrees;
    }
    };

    虽然我感觉思路好像一样,但是人家速度就是快…. 应该是避免了重复运算

  • DFS版

vector<bool> visited 来记录所有访问过的节点
vector<bool> onpath 记录当前DFS访问过的几点

一旦当前路径访问完毕,即重置onpath

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
class Solution {
public:
bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
vector<unordered_set<int>> graph = make_graph(numCourses, prerequisites);
vector<bool> onpath(numCourses, false), visited(numCourses, false);
for (int i = 0; i < numCourses; i++)
if (!visited[i] && dfs_cycle(graph, i, onpath, visited))
return false;
return true;
}
private:
vector<unordered_set<int>> make_graph(int numCourses, vector<pair<int, int>>& prerequisites) {
vector<unordered_set<int>> graph(numCourses);
for (auto pre : prerequisites)
graph[pre.second].insert(pre.first);
return graph;
}
bool dfs_cycle(vector<unordered_set<int>>& graph, int node, vector<bool>& onpath, vector<bool>& visited) {
if (visited[node]) return false;
onpath[node] = visited[node] = true;
for (int neigh : graph[node])
if (onpath[neigh] || dfs_cycle(graph, neigh, onpath, visited))
return true;
return onpath[node] = false;
}
};

207.Course Schedule I &amp; II

https://iii.run/archives/2d43d76d47dd.html

作者

mmmwhy

发布于

2018-09-12

更新于

2021-05-30

许可协议