[leetcode]图算法之判断有向图有无环802. Find Eventual Safe States

「爱情、让人受尽委屈。」 2021-09-28 12:26 293阅读 0赞

### 图算法之判断有向图有无环802. Find Eventual Safe States ###

*  题目
 *  题解
 *  代码
 *  优化（使用DFS+染色）

# 题目 #

[leetcode题目入口][leetcode]

# 题解 #

判断有向图有无环：  
不断删去出度为0的结点以及与之相连的边，  
如果到最后还有点没有删去则证明有环

这个方法可以拓展到无向图

这里注意可以使用一个**队列**，来保存被删去的节点  
不断加入出度为0的节点，  
在反转图中找到与其相连的节点之后再从原图中删去。  
直到队列为空退出循环。

# 代码 #

//判断有向图里有无环
    
    class Solution { 
    public:
        vector<int> eventualSafeNodes(vector<vector<int>>& graph) { 
            int size=graph.size();
            vector<vector<int>> rgraph(size); //制作一个反向图
            for(int i=0;i<size;i++){ 
                rgraph[i].clear();
            }
            queue<int> l; //存储当前出度为0的结点
            
            while(!l.empty()){ 
                l.pop();
            }
            
            vector<int> res;
            res.clear();
            
            
            for(int i=0;i<size;i++){ 
                if(graph[i].size()==0){ 
                    l.push(i); //置入出度为0的结点
                }
                for(int j=0;j<graph[i].size();j++){ 
                    rgraph[graph[i][j]].push_back(i);
                }
            }
            
            
            while(!l.empty()){ 
                int v=l.front();
                l.pop();
                res.push_back(v);
                
                for(int j=0;j<rgraph[v].size();j++){ 
                    int temp=rgraph[v][j];
                    //删除temp->v
                    auto iter=find(graph[temp].begin(),graph[temp].end(),v);
                    graph[temp].erase(iter);
                   // graph[temp].erase(v);
                    if(graph[temp].empty()){ 
                        l.push(temp);
                    }
                    
                }
            }
            sort(res.begin(),res.end());
            return res; 
        }
    };

# 优化（使用DFS+染色） #

使用dfs遍历，假如在遍历过程，遇到已经访问的顶点则return false，点仍然是1，  
同一颗dfs树中的点，假如不存在环，  
在访问回自己的时候标记为2。  
下次dfs进来的时候，如果标记为2，则表示是无环图中的点，但是如果是1，则表示该点所在的图有环。

class Solution { 
    public:
       vector<int> eventualSafeNodes(vector<vector<int>>& graph) { 
           int n = graph.size();
           vector<int> res, color(n); // 0 white, 1 gray, 2 black
           for (int i = 0; i < n; ++i) { 
               if (helper(graph, i, color)) res.push_back(i);
           }
           return res;
       }
       bool helper(vector<vector<int>>& graph, int cur, vector<int>& color) { 
           if (color[cur] > 0) return color[cur] == 2;
           color[cur] = 1;
           for (int i : graph[cur]) { 
               if (color[i] == 2) continue;
               if (color[i] == 1 || !helper(graph, i, color)) { 
                   return false;
               }
           }
           color[cur] = 2;
           return true;
       }
    };

[leetcode]: https://leetcode.com/problems/find-eventual-safe-states/