细胞因子 微信小程序教程 数据算法 Nodepad Android开发 docker安装 bash forms ssh cmd count 微信小游戏开发视频 jq遍历元素 erp项目描述 拼接json字符串 java创建字符串数组 python for循环 python写脚本 python简易教程 java入门教程 java的正则表达式 java使用正则表达式 java初级入门教程 java写入txt文件 java成员变量 java怎么配置环境变量 java特性 java读文件 日历制作模板 轮播图js代码 linux解压tar 易语言多线程 思源黑体cn 方正兰亭字体下载 催眠魔蛙 视频解析软件 vue引入第三方js jarsigner 子节点 pr加速视频
当前位置: 首页 > 学习教程  > 编程语言

Leetcode 802. 找到最终的安全状态 DFS与构建反向图进行拓扑排序

2021/1/13 19:54:50 文章标签: 测试文章如有侵权请发送至邮箱809451989@qq.com投诉后文章立即删除

找到最终的安全状态 在有向图中, 我们从某个节点和每个转向处开始, 沿着图的有向边走。 如果我们到达的节点是终点 (即它没有连出的有向边), 我们停止。 现在, 如果我们最后能走到终点,那么我们的起始节点是最终安全的。 更具体地说, 存在一个自然数 K, 无论选择从…

  1. 找到最终的安全状态
    在有向图中, 我们从某个节点和每个转向处开始, 沿着图的有向边走。 如果我们到达的节点是终点 (即它没有连出的有向边), 我们停止。

现在, 如果我们最后能走到终点,那么我们的起始节点是最终安全的。 更具体地说, 存在一个自然数 K, 无论选择从哪里开始行走, 我们走了不到 K 步后必能停止在一个终点。

哪些节点最终是安全的? 结果返回一个有序的数组。

该有向图有 N 个节点,标签为 0, 1, …, N-1, 其中 N 是 graph 的节点数. 图以以下的形式给出: graph[i] 是节点 j 的一个列表,满足 (i, j) 是图的一条有向边。

示例:
输入:graph = [[1,2],[2,3],[5],[0],[5],[],[]]
输出:[2,4,5,6]
由于题目翻译原因 题目意思可能不太准确
**题目意思是 从一个节点的任何一个邻接的出发 不可能再次回到之前已经走过的节点 也就是不存在环 **

用DFS 递归每个节点的时候 应该检查每个节点的状态以便返回是否有环

用拓扑排序的话 因为题意指出了不存在环 也就是 最后会走到一个出度为0的节点才行 这里我们用出度作为标准 构建反向图即可 为什么要构建反向图 因为我们在传统的拓扑排序 是从入度为0的一个节点进入 在访问它邻接的节点 但是现在我们是从出度为0的节点倒着访问 所以说应该构建反向图来记录下是哪一个节点邻接于当前出度为0的节点

class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        # 1 有环 2 无环 -1 当次搜索
        # not graph[i]代表i没有邻接于任何一个节点 即为终点 是安全的
        # def dfs(graph, i, visit):
        #     if visit[i] == 1: return False
        #     if visit[i] == 2 or not graph[i]: return True
        #     visit[i] = -1
        #     for child in graph[i]:
        #         if visit[child] == -1 or not dfs(graph, child, visit):
        #             visit[i] = 1
        #             return False 
        #     visit[i] = 2
        #     return True 
        # n = len(graph)
        # ans = []
        # visit = [0]*n
        # for i in range(n):
        #     if dfs(graph, i, visit):
        #             ans.append(i)
        # return ans



        # 题目意思为 从当前节点任何一个邻接的节点出发 不可能存在环
        # 也就意味着 到最后出度必然为0 才能称之为安全 
        # 采用拓扑排序 以出度为标准 构建反向图
        n = len(graph)
        reGraph = defaultdict(list)
        degree = [0]*n 
        for u, v in enumerate(graph):  # 邻接表 表示u邻接于v 也就是u -> v
            degree[u] += len(v)  # 记录的是出度
            for child in v:
                reGraph[child].append(u)
        queue = deque([i for i in range(n) if degree[i] == 0])  # 用的是双端队列
        ans = []
        while queue:
            nowNode = queue.popleft()
            ans.append(nowNode)
            for child in reGraph[nowNode]:
                degree[child] -= 1
                if degree[child] == 0:
                    queue.append(child)
        return sorted(ans)  # 题目要求返回的列表有序 

因为leetcode python3环境已经导入了collections 所以说对于defaultdict于deque是可以直接引用的


本文链接: http://www.dtmao.cc/news_show_600201.shtml

附件下载

上一篇:git an error occurred

下一篇:JAVA--一维数组

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?