IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> C++知识库 -> leetcode2022年度刷题分类型总结(十一)图论 (python/c++) -> 正文阅读

[C++知识库]leetcode2022年度刷题分类型总结(十一)图论 (python/c++)

说明:前五题基本都用了两种方法分别解答: DFS 和 拓扑排序
DFS很绕,拓扑排序理解起来更简单,一般都首选拓扑排序

但是像例六这种寻找所有可能路径之类用到回溯会更方便的题,就用DFS

例一:207. 课程表

你这个学期必须选修 numCourses 门课程,记为 0 到 numCourses - 1 。

在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出,其中 prerequisites[i] = [ai, bi] ,表示如果要学习课程 ai 则 必须 先学习课程 bi 。

例如,先修课程对 [0, 1] 表示:想要学习课程 0 ,你需要先完成课程 1 。
请你判断是否可能完成所有课程的学习?如果可以,返回 true ;否则,返回 false

示例 1:

输入:numCourses = 2, prerequisites = [[1,0]]
输出:true
解释:总共有 2 门课程。学习课程 1 之前,你需要完成课程 0 。这是可能的。

class Solution(object):
    def canFinish(self, numCourses, prerequisites):
        """
        :type numCourses: int
        :type prerequisites: List[List[int]]
        :rtype: bool
        """
        
        adj=collections.defaultdict(list)
        deg=collections.Counter() #常用于统计词频
        for prerequisite in prerequisites:
            a,b=prerequisite[0],prerequisite[1] #b指向a。b作为key,a作为val
            adj[b].append(a)
            deg[a]+=1 #统计被指向点的入度,对于只有指向动作、没有被指向动作的点来说,入度默认0
 
        q = collections.deque() ##记录初始入度为0的点的集合
        for u in range(numCourses):
            if deg[u]==0:
                q.append(u)

        res=[]
        while len(q)>0:
            tmp=q.popleft()
            res.append(tmp)
            for v in adj[tmp]:
                deg[v]-=1
                if deg[v]==0:
                    q.append(v)
        # print(res)

        return len(res)==numCourses ##判断是否所有点的入度都可以消为0,若是,则无环,代表可以完成所有问题
## 同理、初始化方式不同的解法
class Solution(object):
    def canFinish(self, numCourses, prerequisites):
        """
        :type numCourses: int
        :type prerequisites: List[List[int]]
        :rtype: bool
        """
        #先建立拓扑图,然后判断是否存在互为先修的情况
        #按照拓扑排序的思路来解的话,正确的思路应该是:
        #先从入度为0(即不需要先修课)的课程开始解决,如果入度都为0,自然True
        #如果入度不为零,从

        graph=[[] for _ in range(numCourses)]
        indegree=[0 for _ in range(numCourses)]

        # graph=collections.defaultdict(list)
        # indegree=collections.defaultdict(int)
        for cur,pre in prerequisites:
            graph[pre].append(cur)
            indegree[cur]+=1

        deque=collections.deque()
        for i in range(len(indegree)):
            if not indegree[i]:
                deque.append(i)

        while deque:
            pre=deque.popleft()
            numCourses-=1
            for cur in graph[pre]:
                indegree[cur]-=1
                if not indegree[cur]:
                    deque.append(cur)

        return not numCourses

例二:210. 课程表 II

现在你总共有 numCourses 门课需要选,记为 0 到 numCourses - 1。给你一个数组 prerequisites ,其中 prerequisites[i] = [ai, bi] ,表示在选修课程 ai 前 必须 先选修 bi 。

例如,想要学习课程 0 ,你需要先完成课程 1 ,我们用一个匹配来表示:[0,1] 。
返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序,你只要返回 任意一种 就可以了。如果不可能完成所有课程,返回 一个空数组 。

示例 1:

输入:numCourses = 2, prerequisites = [[1,0]]
输出:[0,1]
解释:总共有 2 门课程。要学习课程 1,你需要先完成课程 0。因此,正确的课程顺序为 [0,1] 。
示例 2:

输入:numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
输出:[0,2,1,3]
解释:总共有 4 门课程。要学习课程 3,你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。
因此,一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3] 。

Python3 力扣官方DFS解法 比较绕
这里想用python2对代码进行改写,主要改的部分是valid变量。它在函数中的作用是记录是否有环,一旦更改为False就不应再变,即使是递归的回溯也不应该改变它的值。
官方代码用的是nonlocal的声明 。它的作用简单说明:在外部函数先进行声明,在内部函数进行nonlocal声明,这样在内部函数中的变量与外部函数中的同名是同一个变量。
nonlocal说明

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        edges = collections.defaultdict(list)
        # 标记每个节点的状态:0=未搜索,1=搜索中,2=已完成
        visited = [0] * numCourses
        # 用数组来模拟栈,下标 0 为栈底,n-1 为栈顶
        result = list()
        # 判断有向图中是否有环
        valid = True

        for info in prerequisites:
            edges[info[1]].append(info[0])
        
        def dfs(u: int):
            nonlocal valid 
            # 将节点标记为「搜索中」
            visited[u] = 1
            # 搜索其相邻节点
            # 只要发现有环,立刻停止搜索
            for v in edges[u]:
                # 如果「未搜索」那么搜索相邻节点
                if visited[v] == 0:
                    dfs(v)
                    if not valid:
                        return
                # 如果「搜索中」说明找到了环
                elif visited[v] == 1:
                    valid = False
                    return
            # 将节点标记为「已完成」
            visited[u] = 2
            # 将节点入栈
            result.append(u) ###按递归函数的特性,先被标记为「已完成」的节点,一定是有向图最尾端的点(无环时)
        
        # 每次挑选一个「未搜索」的节点,开始进行深度优先搜索
        for i in range(numCourses):
            if valid and not visited[i]:
                dfs(i)
        
        if not valid:
            return list()
        
        # 如果没有环,那么就有拓扑排序
        # 注意下标 0 为栈底,因此需要将数组反序输出
        return result[::-1]

python2版本(通过def init(self):把self.valid声明为全局变量

class Solution(object):
    def __init__(self):
        self.valid=True

    def dfs(self,u,visited,edges,result):
        # 将节点标记为「搜索中」
        visited[u] = 1
        # 搜索其相邻节点
        # 只要发现有环,立刻停止搜索
        for v in edges[u]:
            # 如果「未搜索」那么搜索相邻节点
            if visited[v] == 0:
                self.dfs(v,visited,edges,result)
                if not self.valid:
                    return
            # 如果「搜索中」说明找到了环,因为visited[v]==1说明v节点也还在搜索中,又在u的搜索过程中回到了v 
            # 说明成环了
            elif visited[v] == 1:
                self.valid = False
                return
        # 将节点标记为「已完成」
        visited[u] = 2
        # 将节点入栈
        result.append(u) ##按递归函数的特性,先被标记为「已完成」的节点,一定是有向图最尾端的点(无环时)

    def findOrder(self, numCourses, prerequisites):
        """
        :type numCourses: int
        :type prerequisites: List[List[int]]
        :rtype: List[int]
        """
        # 存储有向图
        edges = collections.defaultdict(list)
        # 标记每个节点的状态:0=未搜索,1=搜索中,2=已完成
        visited = [0] * numCourses
        # 用数组来模拟栈,下标 0 为栈底,n-1 为栈顶
        result = list()
        # 判断有向图中是否有环

        for info in prerequisites:
            edges[info[1]].append(info[0])


        # 每次挑选一个「未搜索」的节点,开始进行深度优先搜索
        for i in range(numCourses):
            if self.valid and not visited[i]:
                self.dfs(i,visited,edges,result)
        
        if not self.valid:
            return list()
        
        # 如果没有环,那么就有拓扑排序
        # 注意下标 0 为栈底,因此需要将数组反序输出
        return result[::-1]  ##需要从头到尾输出

但是平心而论,DFS做关于图论的题实在太麻烦了,所以还是推荐拓扑排序的解法。拓扑排序的定义是BFS和贪心算法应用于有向图的的专有名词。
「拓扑排序」的一个附加效果是:能够顺带检测有向图中是否存在环。如果优先图中,存在环,拓扑排序不能继续得到入度值为 0 的节点,退出循环,此时图中存在没有遍历到的节点,说明图中存在环。(顺丰科技竞赛第一题)

基本代码都换汤不换药

class Solution(object):
    def findOrder(self, numCourses, prerequisites):
        """
        :type numCourses: int
        :type prerequisites: List[List[int]]
        :rtype: List[int]
        """
        adj=[[] for _ in range(numCourses)]
        indeg=[0 for _ in range(numCourses)]

        for prerequisite in prerequisites:
            adj[prerequisite[1]].append(prerequisite[0])
            indeg[prerequisite[0]]+=1

        from collections import deque
        queue=deque()

        for i in range(numCourses):
            if indeg[i]==0:
                queue.append(i)

        res=[]
        while queue:
            top=queue.pop()
            res.append(top)

            for relate in adj[top]: #处理入度为0点的邻接
                indeg[relate]-=1
                if indeg[relate]==0:
                    queue.append(relate) #扩展入度为0的点

        # print(res)

        if len(res)!=numCourses:
            return []
        else:
            return res

例三:851. 喧闹和富有

有一组 n 个人作为实验对象,从 0 到 n - 1 编号,其中每个人都有不同数目的钱,以及不同程度的安静值(quietness)。为了方便起见,我们将编号为 x 的人简称为 "person x "。

给你一个数组 richer ,其中 richer[i] = [ai, bi] 表示 person ai 比 person bi 更有钱。另给你一个整数数组 quiet ,其中 quiet[i] 是 person i 的安静值。richer 中所给出的数据 逻辑自洽(也就是说,在 person x 比 person y 更有钱的同时,不会出现 person y 比 person x 更有钱的情况 )。

现在,返回一个整数数组 answer 作为答案,其中 answer[x] = y 的前提是,在所有拥有的钱肯定不少于 person x 的人中,person y 是最安静的人(也就是安静值 quiet[y] 最小的人)。

示例 1:

输入:richer = [[1,0],[2,1],[3,1],[3,7],[4,3],[5,3],[6,3]], quiet = [3,2,5,4,6,1,7,0]
输出:[5,5,2,5,4,5,6,7]
解释:
answer[0] = 5,
person 5 比 person 3 有更多的钱,person 3 比 person 1 有更多的钱,person 1 比 person 0 有更多的钱。
唯一较为安静(有较低的安静值 quiet[x])的人是 person 7,
但是目前还不清楚他是否比 person 0 更有钱。
answer[7] = 7,
在所有拥有的钱肯定不少于 person 7 的人中(这可能包括 person 3,4,5,6 以及 7),
最安静(有较低安静值 quiet[x])的人是 person 7。
其他的答案也可以用类似的推理来解释。

DFS解法

class Solution(object):
    def loudAndRich(self, richer, quiet):
        """
        :type richer: List[List[int]]
        :type quiet: List[int]
        :rtype: List[int]
        """
        #按照richer数组建立邻接表,规则是从较穷的人指向较富的人
        #题目实际上是求,从某点出发它的可达点中,安静值最小的点
        #step1 首先找到当前人的标号,然后根据这个标号,再richer矩阵中找到比它钱多的人(当前人作为矩阵的第二个元素,然后链式连接,找到每一个钱比它多的人,包括它自己) 有向图的知识点
        n=len(quiet)
        adj=[[] for _ in range(n)]
        for r in richer:
            adj[r[1]].append(r[0])

        ans=[-1]*n #初始化结果数组
        def dfs(x):
            if ans[x]!=-1:
                return
            ans[x]=x
            for y in adj[x]: #x是较穷的人,y是较富的人
                dfs(y) #这里的逻辑是从x出发能抵达到y,然后递归到求y的可达点中,安静值最小的点
                #最后比较y点可达的安静值最小的点是否小于x点可达的安静值最小的点(quiet[ans[y]]<quiet[ans[x]])
                #如果是,更新ans[x]=ans[y]
                if quiet[ans[y]]<quiet[ans[x]]:
                    ans[x]=ans[y]
        for i in range(n):
            dfs(i)
        return ans

拓扑排序解法

class Solution(object):
    def loudAndRich(self, richer, quiet):
        """
        :type richer: List[List[int]]
        :type quiet: List[int]
        :rtype: List[int]
        """
        #按照richer数组建立邻接表,规则是从较富有的人指向较穷的人
        #题目实际上是求,从某点出发它的可达点中,安静值最小的点
        n=len(quiet)
        adj=[[] for _ in range(n)]
        indeg=[0 for _ in range(n)]

        for r in richer:
            adj[r[0]].append(r[1]) #从较富有的人指向较穷的人
            indeg[r[1]]+=1
        
        from collections import deque
        queue=deque()

        for i in range(n):
            if indeg[i]==0:
                queue.append(i)


        ans=list(range(n))  #初始把每个人的答案都设为自己 (钱肯定不少于 person x 的人中,person y 是最安静的人

        while queue:
            top=queue.pop()
            for relate in adj[top]:
                if quiet[ans[top]]<quiet[ans[relate]]: #ans[relate]代表邻接点relate找到的钱肯定不少于自己的人中,且是最安静的人
                    ans[relate]=ans[top]#如果top的答案更安静,且邻接点钱肯定不多于自己(富指向穷,自己富邻接点穷),那么邻接点的答案就要换成top的答案
                indeg[relate]-=1
                if indeg[relate]==0:
                    queue.append(relate)

        return ans

例四:997. 找到小镇的法官

小镇里有 n 个人,按从 1 到 n 的顺序编号。传言称,这些人中有一个暗地里是小镇法官。

如果小镇法官真的存在,那么:

小镇法官不会信任任何人。
每个人(除了小镇法官)都信任这位小镇法官。
只有一个人同时满足属性 1 和属性 2 。
给你一个数组 trust ,其中 trust[i] = [ai, bi] 表示编号为 ai 的人信任编号为 bi 的人。

如果小镇法官存在并且可以确定他的身份,请返回该法官的编号;否则,返回 -1 。

示例 1:

输入:n = 2, trust = [[1,2]]
输出:2

class Solution(object):
    def findJudge(self, n, trust):
        """
        :type n: int
        :type trust: List[List[int]]
        :rtype: int
        """
        ##[ai, bi] 表示编号为 ai 的人信任编号为 bi 的人,有向图从信任者指向被信任的人
        #题意:找出入度为n-1,出度为0的点编号,若没有返回-1
        # adj=[[] for _ in range(n)]
        indeg=[0 for _ in range(n)]
        outdeg=[0 for _ in range(n)]

        for t in trust:
            # adj[t[0]-1].append(t[1]-1) #t[0]指向t[1]
            indeg[t[1]-1]+=1  #按从 1 到 n 的顺序编号,为方便处理的时候全部-1操作,返回答案时加回
            outdeg[t[0]-1]+=1

        for i in range(n):
            if indeg[i]==n-1 and outdeg[i]==0:
                return i+1

        return -1

例五:841. 钥匙和房间

有 n 个房间,房间按从 0 到 n - 1 编号。最初,除 0 号房间外的其余所有房间都被锁住。你的目标是进入所有的房间。然而,你不能在没有获得钥匙的时候进入锁住的房间。

当你进入一个房间,你可能会在里面找到一套不同的钥匙,每把钥匙上都有对应的房间号,即表示钥匙可以打开的房间。你可以拿上所有钥匙去解锁其他房间。

给你一个数组 rooms 其中 rooms[i] 是你进入 i 号房间可以获得的钥匙集合。如果能进入 所有 房间返回 true,否则返回 false。

示例 1:

输入:rooms = [[1],[2],[3],[]]
输出:true
解释:
我们从 0 号房间开始,拿到钥匙 1。
之后我们去 1 号房间,拿到钥匙 2。
然后我们去 2 号房间,拿到钥匙 3。
最后我们去了 3 号房间。
由于我们能够进入每个房间,我们返回 true。

class Solution(object):
    def canVisitAllRooms(self, rooms):
        """
        :type rooms: List[List[int]]
        :rtype: bool
        """
        #题目可以首先通过dfs递归记录所有房间的是否被访问过
        n=len(rooms)
        visited=[False for _ in range(n)]

        def dfs(key,visited,rooms):# key代表访问的房间号
            if visited[key]:# 循环退出条件为如果此房间已经访问过,则return
                return  #退出条件避免了死循环,又把能访问到的都标上了True

            visited[key]=True
            m=len(rooms[key])
            # print(visited)
            for i in range(m):
                dfs(rooms[key][i],visited,rooms) 

        dfs(0,visited,rooms)

        # print(visited)

        for i in range(n):
            if not visited[i]:
                return False
       
        return True

拓扑排序方法

class Solution(object):
    def canVisitAllRooms(self, rooms):
        """
        :type rooms: List[List[int]]
        :rtype: bool
        """
        n=len(rooms)

        visited=[False for _ in range(n)]

        from collections import deque
        queue=deque()

        queue.append(rooms[0])
        visited[0]=True

        while queue:
            top=queue.pop()

            if not top:
                continue
            for i in top:
                if visited[i]: #已经去过就不继续去了
                    continue
                queue.append(rooms[i]) #拿到i号房间钥匙 去i号房间
                visited[i]=True #i号房间已经去过

        for i in range(n):
            if not visited[i]:
                return False

        return True

例六:797. 所有可能的路径

给你一个有 n 个节点的 有向无环图(DAG),请你找出所有从节点 0 到节点 n-1 的路径并输出(不要求按特定顺序)

graph[i] 是一个从节点 i 可以访问的所有节点的列表(即从节点 i 到节点 graph[i][j]存在一条有向边)。

输入:graph = [[1,2],[3],[3],[]]
输出:[[0,1,3],[0,2,3]]
解释:有两条路径 0 -> 1 -> 3 和 0 -> 2 -> 3

class Solution(object):
    def allPathsSourceTarget(self, graph):
        """
        :type graph: List[List[int]]
        :rtype: List[List[int]]
        """
        #此题特殊在graph本身就是邻接表,不用额外操作
        n=len(graph) 
        ans=[]

        def dfs(key,graph,path):
            if key>=n-1:  #找出所有从节点 0 到节点 n-1 的路径并输出 最后终点都是n-1
                # path.append(key)
                ans.append(path[:])
                # print(path)
                return 
            for relate in graph[key]:
                dfs(relate,graph,path+[relate]) ##此处利用了递归函数的回溯

        dfs(0,graph,[0])
        return ans

例七:802. 找到最终的安全状态

有一个有 n 个节点的有向图,节点按 0 到 n - 1 编号。图由一个 索引从 0 开始 的 2D 整数数组 graph表示, graph[i]是与节点 i 相邻的节点的整数数组,这意味着从节点 i 到 graph[i]中的每个节点都有一条边。

如果一个节点没有连出的有向边,则它是 终端节点 。如果没有出边,则节点为终端节点。如果从该节点开始的所有可能路径都通向 终端节点 ,则该节点为 安全节点 。

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

输入:graph = [[1,2],[2,3],[5],[0],[5],[],[]]
输出:[2,4,5,6]
解释:示意图如上。
节点 5 和节点 6 是终端节点,因为它们都没有出边。
从节点 2、4、5 和 6 开始的所有路径都指向节点 5 或 6 。

class Solution(object):
    def eventualSafeNodes(self, graph):
        """
        :type graph: List[List[int]]
        :rtype: List[int]
        """

        #解法一:深度优先搜索+三色标记
        #重要的在于理解题意,本题的安全状态其实就是指以i为起始点遍历,遍历下去不成环的节点
        #因为只要不成环,都能最后指向终端节点
        #用深度优先搜索+三色标记可以得到i作为起始点是否成环的标记

        # n = len(graph)
        # color = [0] * n # 0未完成 1在进行 2已完成

        # def safe(x):
        #     if color[x] > 0:
        #         return color[x] == 2
        #     color[x] = 1  ##如果点x
        #     for y in graph[x]:
        #         if not safe(y):
        #             return False
        #     color[x] = 2
        #     # 如果dfs遍历下去均未遍历回来,则说明该点不在环里,属于安全结点,修改状态并返回True
        #     return True

        # return [i for i in range(n) if safe(i)]

        #解法二:反图+拓扑排序
        #此题graph即是邻接表,不用再重建
        #如果从该节点开始的所有可能路径都通向 终端节点 ,则该节点为 安全节点 。

        #需要求每个节点出度,出度为0的是终端节点
        #如果做成反图,那就是求入度为0的是终端节点,以及最终入度可以为0的节点
        n=len(graph)

        indeg=[0 for _ in range(n)]
        adj=[[] for _ in range(n)]

        for x,ys in enumerate(graph): #graph:x指向y 
            for y in ys:
                adj[y].append(x) #adj:y指向x 
                indeg[x]+=1

        #现在求入度为0的点
        from collections import deque
        queue=deque()

        for i in range(n):
            if indeg[i]==0:
                queue.append(i)

        # res=[] 
        while queue:
            top=queue.pop()
            # res.append(top)
            for relate in adj[top]:
                indeg[relate]-=1
                if indeg[relate]==0:
                    queue.append(relate)

        # res.sort()
        # return res #返回结果的方式有两种,一种是直接定义一个res 存结果,但由于要求结果正序排列,还需要res.sort()会增加时间复杂度
        return [i for i, d in enumerate(indeg) if d == 0] #一种直接使用indeg,如果indeg[i]==0,返回它的下标
  C++知识库 最新文章
【C++】友元、嵌套类、异常、RTTI、类型转换
通讯录的思路与实现(C语言)
C++PrimerPlus 第七章 函数-C++的编程模块(
Problem C: 算法9-9~9-12:平衡二叉树的基本
MSVC C++ UTF-8编程
C++进阶 多态原理
简单string类c++实现
我的年度总结
【C语言】以深厚地基筑伟岸高楼-基础篇(六
c语言常见错误合集
上一篇文章      下一篇文章      查看所有文章
加:2022-06-29 18:48:02  更:2022-06-29 18:51:30 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年3日历 -2024/3/29 8:41:31-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码