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

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 创作，最后编辑时间为: Sep 12, 2018 at 03:34 pm

Course Schedule I & II

207. Course Schedule

题目

思路1

代码1

思考