课程表规划问题,一般来说主要考虑是否存在环。
207. Course Schedule
题目
207. Course Schedule
是否存在环
Input: 2, [[1,0],[0,1]]
Output: false
思路1
我自己想了一个思路,就是从入度着手。
1、把所有入度为0的节点找出来,从这些节点开始。(为什么不用别的节点?没用啊,既然入度不是0,那么这个节点肯定包含在另外一个入度是0节点构造的树中)。
2、然后把这几个入度是0的节点删除
3、循环1->2
,直到找不到新的入度为0的节点,这个时候,如果所有节点都被访问过了,那么无环。否则有环 /如果有环的话,每个节点都入度出度为1。
代码1
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版
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
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;
}
};
本文由 mmmwhy 创作,最后编辑时间为: May 2, 2019 at 01:46 pm