LeetCode_802找到最终的安全状态（dfs）_leetcode 802

题目链接：https://leetcode-cn.com/problems/find-eventual-safe-states/description/

        本题大意就是找出所有不与环连通的结点。不安全状态有两种情况：1、这个点在一个环中。2、这个点顺着边递推，会走到一个环里。所以本题的思路是给点设置三种状态，初始时的0表示未访问过的点；1表示这个点是不安全的，即这个点连接着一个环或就在环中；2表示这个点是安全的，不与任何环连通。然后对每个点进行深度优先搜索，若遇到了不安全的点，那么这个点也是不安全的，置为2。若遇到了安全的点，则表示已经有了一条可以通向终点的路径，那么这个点也是安全的，置为2。代码如下：

class Solution {
public:
	bool dfs(int i,vector<int>& color,vector<vector<int> >& gra)
	{
		//若这个点为0，则进行下面的访问操作，否则返回这个点的状态 
		if(color[i])
			return color[i]==2;
		//在未到达终点前，所有点都是不安全的。 
		color[i]=1;
		//深度优先搜索 
		for(int j=0;j<gra[i].size();j++)
		{
			//若下个点是不安全的则返回false，且不会将这个点的状态该为2，表示这个点不安全。
			if(color[gra[i][j]]==1 || !dfs(gra[i][j],color,gra))
				return false;
		}
		//若走到了终点，则给他置为2，且返回true
		color[i]=2;
		return true;
	}
    vector<int> eventualSafeNodes(vector<vector<int> >& graph) {
    	int n=graph.size();
        vector<int> res;
        vector<int> color(n,0);
        //对每个点进行搜索，将安全的点加入结果集中 
        for(int i=0;i<n;i++)
        	if(dfs(i,color,graph))
        		res.push_back(i);
        return res;
    }
};