207.Course Schedule I & II

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

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;
    }
};