說明：前五題基本都用了兩種方法分別解答： DFS 和 拓撲排序
DFS很繞，拓撲排序理解起來更簡單，一般都首選拓撲排序
但是像例六這種尋找所有可能路徑之類用到回溯會更方便的題，就用DFS
你這個學期必須選修 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
現在你總共有 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
有一組 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
小鎮裡有 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
有 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
給你一個有 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
有一個有 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，返回它的下標
