[Python知识库]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，返回它的下标