反向图+拓扑排序 or 染色：Leetcode802 找到最终的安全状态

问题：

思路：

反向图+拓扑排序：

对于一个节点 u，如果我们从 u 开始任意行走能够走到一个环里，那么 u 就不是一个安全的节点。换句话说，u 是一个安全的节点，当且仅当 u 直接相连的节点（u 的出边相连的那些节点）都是安全的节点。

对于没有出度的节点，一定是最终安全的节点，而仅直接指向它的节点（出度为1，且指向没有出度的节点）也是最终安全的节点。以此类推，这样我们可以将所有的边全部反向，首先所有没有任何入度的节点都是安全的，我们把这些节点全部移除。随后新的图中没有任何入度的节点都是安全的。

我们发现这种做法实际上就是对图进行拓扑排序，将原问题转化为了拓扑排序问题

染色：

对于每个节点，有三种染色方法：白色表示节点尚未被访问（用0表示），灰色表示该节点在此轮搜索中已被访问过或该节点在环中（用1表示），黑色表示该节点的所有相连节点已被访问，且该节点不在环中（用2表示）

对每个节点进行DFS，DFS函数的功能为判断该节点是否为黑色节点或能被染成黑色。
进入DFS后，判断该节点是否已经被染过色，若已染成黑色，直接返回TRUE，染成灰色直接返回FALSE
若未被染色，先将其染成灰色
只有与该节点相连的所有节点都为黑色节点或能被染成黑色，该节点才能被染成黑色，并返回TRUE（u 是一个安全的节点，当且仅当 u 直接相连的节点都是安全的节点），否则返回FALSE

代码：

反向图+拓扑排序：

class Solution {
public:
    vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
        int* indegree;
        vector<int> ans;
        indegree=(int*)malloc( graph.size()*sizeof(int) );
        int i;
        for( i=0;i<graph.size();i++ )
        {
            indegree[i]=0;
        }
        int j;
        for( i=0;i<graph.size();i++ )
            indegree[i]=graph[i].size();
        vector<vector<int>> reverse_graph;
        for( i=0;i<graph.size();i++ )
            reverse_graph.push_back( vector<int>() );
        for( i=0;i<graph.size();i++ )
        {
            for( j=0;j<graph[i].size();j++ )
                reverse_graph[ graph[i][j] ].push_back(i);
        }
        stack<int> st;
        for( i=0;i<graph.size();i++ )
        {
            if( indegree[i]==0 )
                st.push( i );
        }
        int temp;
        while( st.size()!=0 )
        {
            temp=st.top();
            ans.push_back(temp);
            st.pop();
            for( i=0;i<reverse_graph[temp].size();i++ )
            {
                indegree[ reverse_graph[temp][i] ]--;
                if( indegree[ reverse_graph[temp][i] ]==0 )
                    st.push( reverse_graph[temp][i] );
            }
        }
        sort( ans.begin(),ans.end() );
        return ans; 
    }
};

染色：

class Solution {
public:
    bool dfs( int i,vector<vector<int>>& graph,int* color )
    {
        if( color[i]>0 )
            return color[i]==2;
        color[i]=1;
        int j;
        for( j=0;j<graph[i].size();j++ )
        {   
            if( color[ graph[i][j] ]==2 )
                continue;
            else if( color[ graph[i][j] ]==1 || !dfs( graph[i][j],graph,color ) )
                return false;
        }
        color[i]=2;
        return true;
    }
    vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
        int* color;
        color=(int*)malloc( graph.size()*sizeof(int) );
        int i;
        for( i=0;i<graph.size();i++ )
            color[i]=0;
        vector<int> ans;
        for( i=0;i<graph.size();i++ )
        {
            if( dfs( i,graph,color ) )
                ans.push_back(i);
        }
        return ans;
    }
};