一起学习交流~

找到最终的安全状态-DFS+拓扑排序

算法 laomuji 7个月前 (03-06) 430次浏览 已收录 0个评论

题目

链接
https://leetcode-cn.com/problems/find-eventual-safe-states/

在有向图中,以某个节点为起始节点,从该点出发,每一步沿着图中的一条有向边行走。如果到达的节点是终点(即它没有连出的有向边),则停止。

对于一个起始节点,如果从该节点出发,无论每一步选择沿哪条有向边行走,最后必然在有限步内到达终点,则将该起始节点称作是 安全 的。

返回一个由图中所有安全的起始节点组成的数组作为答案。答案数组中的元素应当按 升序 排列。

该有向图有 n 个节点,按 0 到 n – 1 编号,其中 n 是 graph 的节点数。图以下述形式给出:graph[i] 是编号 j 节点的一个列表,满足 (i, j) 是图的一条有向边。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/find-eventual-safe-states
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

DFS

用DFS很容易解决,不废话,直接上代码

class Solution {
/*
0到1,
1到2,2到5,5无连接,访问完毕,标记安全,返回true
1到3,3到0,0已经访问过了,表示有环,返回false,回溯到0,false
*/
private:
    enum STATUS{UNVISIT,VISITED,SAFE};//未访问,已访问,安全
public:
    vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
        vector<int>result;
        vector<STATUS>status(graph.size(),STATUS::UNVISIT);//各节点的状态
        for(int i =0;i<graph.size();i++){
            //如果已经访问了,不是安全的那么就是不安全的,不需要处理
            if(status[i]==STATUS::VISITED) continue;
            //如果没有访问,那么就dfs搜索
            if(status[i]==STATUS::UNVISIT){
                dfs(graph,i,status);
            }
            //若当前节点是安全的,就添加进结果
            if(status[i]==STATUS::SAFE) result.push_back(i);
        }
        return result;
    }

    bool dfs(vector<vector<int>>& graph,int index,vector<STATUS>&status){
        if(status[index]==STATUS::SAFE)return true;//如果已经是安全的了,直接返回true
        if(status[index]==STATUS::VISITED)return false;//如果已经访问过了,返回false,表示成环了
        status[index] = STATUS::VISITED;//标记为已访问
        //只要有一个相连的是不安全的,那么当前节点就是不安全的
        for(int i=0;i<graph[index].size();i++){
            if(dfs(graph,graph[index][i],status)==false)return false;
        }
        status[index] = STATUS::SAFE;//标记为安全
        return true;
    }
};

拓扑排序

需要逆转一下拓扑排序的思路,把图反向存,交换入度和出度即可

class Solution {
/*
拓扑排序是按照入度为0的
这个题相反,需要采用出度为0的
出度为0,一定不会成环,此时可以将指向当前点的点的出度-1
*/
public:
    vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
        int size = graph.size();
        vector<int>outDegrees(size);
        vector<vector<int>>edges(size);//反向存图 存所有指向第i个节点的节点
        queue<int>que;//存放出度为0的队列
        vector<int>result;
        for(int u =0;u<size;u++){
            for(int j =0;j<graph[u].size();j++){
                int v = graph[u][j];
                edges[v].push_back(u);
            }
            outDegrees[u]=graph[u].size();//计算出度
            if(outDegrees[u]==0)que.push(u);//把出度为0的加入队列
        }
        while(que.size()){
            int v = que.front();que.pop();
            for(int i =0;i<edges[v].size();i++){
                int u = edges[v][i];
                outDegrees[u]--;//减少出度
                if(outDegrees[u]==0)que.push(u);//把出度为0的加入队列
            }
        }
        for(int i=0;i<outDegrees.size();i++){
            if(outDegrees[i]==0)result.push_back(i);
        }
        sort(result.begin(),result.end());
        return result;
    }
};

效率

喜欢 (0)
订阅评论
提醒
guest
0 评论
内联反馈
查看所有评论