题目链接：
1、Course Schedule https://leetcode.com/problems/course-schedule/
2、Find Eventual Safe States https://leetcode.com/problems/find-eventual-safe-states/
这两题有相似性很高，区别在于第一题是判断这个图中有没有环，第二题是找出连接图中环的节点以及环上的节点
这是DFS专栏，所以暂时不考虑BFS解法
第一题其实很像拓扑排序，但是向无环图（DAG）是拓扑排序的充要条件。题目的本意是要判断是不是DAG，所以和拓扑排序还是 有点差别。（拓扑排序也有DFS和两种解法）
解法1：
使用visit数组来保存图中每一个节点的访问情况，visit[i] = 1表示 i 节点被访问了。（本解法不适用第二题，会出现TLE）
//
class Solution {
public:
// if loop, return true
bool dfs(int node,vector<int>& visit, vector<vector<int>>& graph)
{
if(visit[node] == 1)
{
return true;
}
visit[node] = 1;
vector<int> temp = graph[node];
for(int i=0;i<graph[node].size();i++)
{
if(dfs(temp[i],visit,graph))
{
return true;
}
/*//will TLE
vector<int> temp = prerequisites[i];
if(temp[1] == node )//&& visit[temp[0]] == 0)
{
if(dfs(temp[0],visit,prerequisites))
{
return true;
}
}
*/
}
visit[node] = 0;
return false;
}
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
vector<int> visit(numCourses,0);
vector<vector<int>> graph(numCourses, vector<int>());
for(int j=0;j<prerequisites.size();j++)
{
vector<int> temp = prerequisites[j];
graph[temp[1]].push_back(temp[0]);
//graph[prerequisites[j][1]].push_back(prerequisites[j][0]);
}
for(int i=0;i<numCourses;i++)
{
if(dfs(i,visit,graph))
{
return false;
}
}
return true;
}
};
解法2：
如同解法1一样，使用visit数组来保存图中每一个节点的访问情况，不同于解法1的是，visit数组包括初始状态0会有3个状态，visit[i] = 1表示 i 节点正在被访问，visit[i] = 2表示 i 节点已经被访问过了。visit[i] = 2意味着 i 节点的没有其他的延伸节点可以再被访问了。“没有其他的延伸节点可以再被访问了”有两种情形：一是这个节点没有出度，二是该节点的连接节点没有其他的延伸节点可以再被访问了。
可以看到看到“没有其他的延伸节点可以再被访问了”是一种递归
算法步骤：从图中的任意节点开始进行遍历，标记该节点为正在访问，搜索该节点的其它连接节点，若是其它连接节点会出现环，则结束算法，否则就走下去，直到所有节点都已经被遍历过，标记该节点为已经被访问了
//
class Solution {
public:
// if loop, return true
bool dfs(int node,vector<int>& visit, vector<vector<int>>& graph)
{
if(visit[node] == 2)
{
return false;
}
if(visit[node] == 1)
{
return true;
}
visit[node] = 1;
vector<int> temp = graph[node];
for(int i=0;i<graph[node].size();i++)
{
if(dfs(temp[i],visit,graph))
{
return true;
}
/*//will TLE
vector<int> temp = prerequisites[i];
if(temp[1] == node )//&& visit[temp[0]] == 0)
{
if(dfs(temp[0],visit,prerequisites))
{
return true;
}
}
*/
}
visit[node] = 2;
return false;
}
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
vector<int> visit(numCourses,0);
vector<vector<int>> graph(numCourses, vector<int>());
for(int j=0;j<prerequisites.size();j++)
{
vector<int> temp = prerequisites[j];
graph[temp[1]].push_back(temp[0]);
//graph[prerequisites[j][1]].push_back(prerequisites[j][0]);
}
for(int i=0;i<numCourses;i++)
{
if(dfs(i,visit,graph))
{
return false;
}
}
return true;
}
};
Note:
1、prerequisites要处理成graph，若是在dfs中直接使用prerequisites（如dfs中注释所示），会出现TLE。
2、graph传参时候需要注意使用引用，若是值传递会出现TLE。（传递的是STL容器，对象使用引用传递，int，char这种使用值传递）
3、解法2的效率要比解法1的效率好，解法1中只有两个状态，其visit[i] = 0 状态是包括了解法2中visit[i] = 2和visit[i] = 0两种状态，visit[i] = 1 如同解法2中的 visit[i] = 1。由于visit[i] = 0 的多义性造成了多余深搜。
4、canFinish函数调用dfs在循环之内是因为可能图并不是连通图。
图后期补上……