explain ： The first five questions are basically solved in two ways ： DFS and A topological sort
DFS Very winding , Topological sorting is easier to understand , Topology sorting is generally preferred
But for example 6, it is more convenient to use backtracking to find all possible paths , Just use DFS
You must take this semester numCourses Courses , Write it down as 0 To numCourses - 1 .
Before you take some courses, you need some prerequisite courses . Prerequisite courses by array prerequisites give , among prerequisites[i] = [ai, bi] , If you want to learn a course ai be must Learn the course first bi .
for example , The prerequisite course is right for [0, 1] Express ： Want to learn the course 0 , You need to finish the course first 1 .
Please judge whether it is possible to complete all the courses ？ If possible , return true ; otherwise , return false
Example 1：
Input ：numCourses = 2, prerequisites = [[1,0]]
Output ：true
explain ： All in all 2 Courses . Study the course 1 Before , You need to complete the course 0 . It's possible .
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() # It is often used to count word frequency
for prerequisite in prerequisites:
a,b=prerequisite[0],prerequisite[1] #b Point to a.b As key,a As val
adj[b].append(a)
deg[a]+=1 # Count the penetration of the pointed point , For only pointing actions 、 Points that are not pointed to actions , The default value is 0
q = collections.deque() ## Record the initial penetration as 0 Set of points for
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 ## Determine whether the penetration of all points can be reduced to 0, if , Then there is no ring , Delegates can complete all questions
## Empathy 、 Different initialization methods
class Solution(object):
def canFinish(self, numCourses, prerequisites):
""" :type numCourses: int :type prerequisites: List[List[int]] :rtype: bool """
# First, create a topology diagram , And then judge whether there is a case of mutual repair
# If it is solved according to the idea of topological sorting , The right way of thinking should be ：
# The first step is 0（ That is, there is no need to take a course first ） The course begins to solve , If the penetration is 0, natural True
# If the penetration is not zero , from
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
Now you have numCourses Courses need to be selected , Write it down as 0 To numCourses - 1. Give you an array prerequisites , among prerequisites[i] = [ai, bi] , In elective courses ai front must First elective bi .
for example , Want to learn the course 0 , You need to finish the course first 1 , We use a match to represent ：[0,1] .
Return to the learning order you arranged to complete all the courses . There may be more than one correct order , You just go back Any one That's all right. . If it is not possible to complete all the courses , return An empty array .
Example 1：
Input ：numCourses = 2, prerequisites = [[1,0]]
Output ：[0,1]
explain ： All in all 2 Courses . To learn the course 1, You need to finish the course first 0. therefore , The correct order of courses is [0,1] .
Example 2：
Input ：numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output ：[0,2,1,3]
explain ： All in all 4 Courses . To learn the course 3, You should finish the course first 1 And courses 2. And the curriculum 1 And courses 2 They should all be in the class 0 after .
therefore , A correct sequence of courses is [0,1,2,3] . The other right sort is [0,2,1,3] .
Python3 The official DFS solution More winding
I want to use python2 Rewrite the code , The main changes are valid Variable . Its function is to record whether there is a ring , Once changed to False Should not change again , Even recursive backtracking should not change its value .
The official code is nonlocal Statement of . Its function is simply explained ： Declare in the external function first , In the internal function nonlocal Statement , Thus, the variable in the internal function and the variable with the same name in the external function are the same variable .
nonlocal explain
class Solution:
def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
edges = collections.defaultdict(list)
# Mark the status of each node ：0= Not searched ,1= Searching ,2= Completed
visited = [0] * numCourses
# Use arrays to simulate stacks , Subscript 0 It's the bottom of the stack ,n-1 For the top of the stack
result = list()
# Judge whether there is a ring in a directed graph
valid = True
for info in prerequisites:
edges[info[1]].append(info[0])
def dfs(u: int):
nonlocal valid
# Mark the node as 「 Searching 」
visited[u] = 1
# Search its adjacent nodes
# Just find a ring , Stop searching now
for v in edges[u]:
# If 「 Not searched 」 Then search for adjacent nodes
if visited[v] == 0:
dfs(v)
if not valid:
return
# If 「 Searching 」 That means we found the ring
elif visited[v] == 1:
valid = False
return
# Mark the node as 「 Completed 」
visited[u] = 2
# Putting nodes on the stack
result.append(u) ### According to the characteristics of recursive functions , First marked as 「 Completed 」 The node of , It must be the last point of a digraph （ Acyclic time ）
# Pick one at a time 「 Not searched 」 The node of , Start depth first search
for i in range(numCourses):
if valid and not visited[i]:
dfs(i)
if not valid:
return list()
# If there is no ring , Then there is topological sorting
# Pay attention to the subscript 0 It's the bottom of the stack , Therefore, you need to output the array in reverse order
return result[::-1]
python2 edition （ adopt def init(self): hold self.valid Declare as a global variable ）
class Solution(object):
def __init__(self):
self.valid=True
def dfs(self,u,visited,edges,result):
# Mark the node as 「 Searching 」
visited[u] = 1
# Search its adjacent nodes
# Just find a ring , Stop searching now
for v in edges[u]:
# If 「 Not searched 」 Then search for adjacent nodes
if visited[v] == 0:
self.dfs(v,visited,edges,result)
if not self.valid:
return
# If 「 Searching 」 That means we found the ring , because visited[v]==1 explain v Nodes are still searching , And in the u In the search process, I returned to v
# It means the ring is formed
elif visited[v] == 1:
self.valid = False
return
# Mark the node as 「 Completed 」
visited[u] = 2
# Putting nodes on the stack
result.append(u) ## According to the characteristics of recursive functions , First marked as 「 Completed 」 The node of , It must be the last point of a digraph （ Acyclic time ）
def findOrder(self, numCourses, prerequisites):
""" :type numCourses: int :type prerequisites: List[List[int]] :rtype: List[int] """
# Store digraphs
edges = collections.defaultdict(list)
# Mark the status of each node ：0= Not searched ,1= Searching ,2= Completed
visited = [0] * numCourses
# Use arrays to simulate stacks , Subscript 0 It's the bottom of the stack ,n-1 For the top of the stack
result = list()
# Judge whether there is a ring in a directed graph
for info in prerequisites:
edges[info[1]].append(info[0])
# Pick one at a time 「 Not searched 」 The node of , Start depth first search
for i in range(numCourses):
if self.valid and not visited[i]:
self.dfs(i,visited,edges,result)
if not self.valid:
return list()
# If there is no ring , Then there is topological sorting
# Pay attention to the subscript 0 It's the bottom of the stack , Therefore, you need to output the array in reverse order
return result[::-1] ## You need to output from beginning to end
But to be fair ,DFS It's too much trouble to do the problem about graph theory , Therefore, the solution of topological sorting is recommended . The definition of topological sorting is BFS And greedy algorithm are applied to the proper nouns of directed graphs .
「 A topological sort 」 One added effect of is ： It can detect whether there are rings in the directed graph . If... In the priority diagram , Existential ring , Topological sorting cannot continue to get the penetration value is 0 The node of , Exit loop , At this point, there are nodes in the graph that have not been traversed , It shows that there are rings in the graph .（ The first question of SF technology competition ）
The basic code has changed soup without changing medicine
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]: # The processing depth is 0 Adjacency of points
indeg[relate]-=1
if indeg[relate]==0:
queue.append(relate) # The extension depth is 0 The point of
# print(res)
if len(res)!=numCourses:
return []
else:
return res
There is a group n Individuals as subjects , from 0 To n - 1 Number , Each of them has a different amount of money , And different levels of quiet value （quietness）. For convenience , We'll number it x The person of is abbreviated as "person x ".
Give you an array richer , among richer[i] = [ai, bi] Express person ai Than person bi More money . Give you another integer array quiet , among quiet[i] yes person i Quiet value of .richer The data given in Self-consistent logic （ in other words , stay person x Than person y More money at the same time , There will be no person y Than person x More money ）.
Now? , Returns an array of integers answer As the answer , among answer[x] = y The premise is , There must be no less than person x Of the people ,person y Is the quietest person （ That is, quiet value quiet[y] The youngest ）.
Example 1：
Input ：richer = [[1,0],[2,1],[3,1],[3,7],[4,3],[5,3],[6,3]], quiet = [3,2,5,4,6,1,7,0]
Output ：[5,5,2,5,4,5,6,7]
explain ：
answer[0] = 5,
person 5 Than person 3 There's more money ,person 3 Than person 1 There's more money ,person 1 Than person 0 There's more money .
Only quieter （ There is a lower quiet value quiet[x]） The people are person 7,
But it's not clear if he is better than person 0 More money .
answer[7] = 7,
There must be no less than person 7 Of the people （ This may include person 3,4,5,6 as well as 7）,
The quietest （ There is a lower quiet value quiet[x]） The people are person 7.
Other answers can be explained by similar reasoning .
DFS solution
class Solution(object):
def loudAndRich(self, richer, quiet):
""" :type richer: List[List[int]] :type quiet: List[int] :rtype: List[int] """
# according to richer Array to establish adjacency table , The rule is from the poorer to the richer
# The question is actually asking , One of its reachable points from a certain point , The point with the lowest quiet value
#step1 First find the current person's label , Then according to this label , Again richer Find people in the matrix who have more money than it （ The current person is the second element of the matrix , Then chain connection , Find everyone who has more money than it , Including itself ） Knowledge points of digraph
n=len(quiet)
adj=[[] for _ in range(n)]
for r in richer:
adj[r[1]].append(r[0])
ans=[-1]*n # Initializing the result array
def dfs(x):
if ans[x]!=-1:
return
ans[x]=x
for y in adj[x]: #x The poorer people ,y Are the richer people
dfs(y) # The logic here is from x We can arrive at y, Then recurse to find y In the reachable point of , The point with the lowest quiet value
# Last comparison y Whether the point at which the minimum quiet value can be reached is less than x The point at which the minimum quiet value can be reached (quiet[ans[y]]<quiet[ans[x]])
# If it is , to update ans[x]=ans[y]
if quiet[ans[y]]<quiet[ans[x]]:
ans[x]=ans[y]
for i in range(n):
dfs(i)
return ans
Topological sorting solution
class Solution(object):
def loudAndRich(self, richer, quiet):
""" :type richer: List[List[int]] :type quiet: List[int] :rtype: List[int] """
# according to richer Array to establish adjacency table , The rule is from the wealthier to the poorer
# The question is actually asking , One of its reachable points from a certain point , The point with the lowest quiet value
n=len(quiet)
adj=[[] for _ in range(n)]
indeg=[0 for _ in range(n)]
for r in richer:
adj[r[0]].append(r[1]) # From the richer to the poorer
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)) # At the beginning, set everyone's answer as yourself （ The money must be no less than person x Of the people ,person y Is the quietest person
while queue:
top=queue.pop()
for relate in adj[top]:
if quiet[ans[top]]<quiet[ans[relate]]: #ans[relate] Represents the adjacency point relate Of those who have found no less money than themselves , And the quietest person
ans[relate]=ans[top]# If top The answer is quieter , And the neighbor must have no more money than himself （ The rich point to the poor , I am rich and my neighbors are poor ）, Then the answer of the adjacent node should be changed to top The answer
indeg[relate]-=1
if indeg[relate]==0:
queue.append(relate)
return ans
There are in the town n personal , Press from 1 To n The sequence number of . rumors , One of these people is secretly a town judge .
If the town judge really exists , that ：
The town judge won't trust anyone .
everyone （ Except for the town judge ） Trust the town judge .
Only one person satisfies attributes at the same time 1 And attribute 2 .
Give you an array trust , among trust[i] = [ai, bi] Indicates that the number is ai The person's trust number is bi People who .
If the town judge exists and can identify him , Please return the judge's number ; otherwise , return -1 .
Example 1：
Input ：n = 2, trust = [[1,2]]
Output ：2
class Solution(object):
def findJudge(self, n, trust):
""" :type n: int :type trust: List[List[int]] :rtype: int """
##[ai, bi] Indicates that the number is ai The person's trust number is bi People who , The directed graph points from the trustor to the trusted person
# The question ： Find out if the degree of penetration is n-1, The degree of 0 Point number of , If you don't return -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] Point to t[1]
indeg[t[1]-1]+=1 # Press from 1 To n The sequence number of , For the convenience of handling all the time -1 operation , Add... When returning the answer
outdeg[t[0]-1]+=1
for i in range(n):
if indeg[i]==n-1 and outdeg[i]==0:
return i+1
return -1
Yes n A room , The room is from 0 To n - 1 Number . first , except 0 All the other rooms outside room No . Your goal is to enter all the rooms . However , You can't enter a locked room without getting the key .
When you enter a room , You may find a different set of keys in it , Each key has a corresponding room number , It means that the key can open the room . You can take all the keys to unlock other rooms .
Give you an array rooms among rooms[i] You entered i A collection of keys available in room . If you can get into all Room return true, Otherwise return to false.
Example 1：
Input ：rooms = [[1],[2],[3],[]]
Output ：true
explain ：
We from 0 Room No , Get the key 1.
Then we go to 1 Room number , Get the key 2.
Then we go 2 Room number , Get the key 3.
At last we went to 3 Room number .
Because we can get into every room , We go back to true.
class Solution(object):
def canVisitAllRooms(self, rooms):
""" :type rooms: List[List[int]] :rtype: bool """
# The title can be passed first dfs Recursively record whether all rooms have been visited
n=len(rooms)
visited=[False for _ in range(n)]
def dfs(key,visited,rooms):# key Room number visited by the representative
if visited[key]:# The cycle exit condition is if this room has been visited , be return
return # Exit conditions avoid dead loops , Again, I marked all that I could access 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
Topological sorting method
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]: # If you have already been there, don't go on
continue
queue.append(rooms[i]) # Get i Room key No Go to i Room number
visited[i]=True #i Room has been to
for i in range(n):
if not visited[i]:
return False
return True
Here you are n Of nodes Directed acyclic graph （DAG）, Please find all slave nodes 0 To the node n-1 And output （ No specific order is required ）
graph[i] Is a slave node i List of all nodes that can be accessed （ That is, the slave node i To the node graph[i][j] There is a directed side ）.
Input ：graph = [[1,2],[3],[3],[]]
Output ：[[0,1,3],[0,2,3]]
explain ： There are two paths 0 -> 1 -> 3 and 0 -> 2 -> 3
class Solution(object):
def allPathsSourceTarget(self, graph):
""" :type graph: List[List[int]] :rtype: List[List[int]] """
# This question is special in graph Itself is the adjacency table , No extra operation
n=len(graph)
ans=[]
def dfs(key,graph,path):
if key>=n-1: # Find all slave nodes 0 To the node n-1 And output The final destination is n-1
# path.append(key)
ans.append(path[:])
# print(path)
return
for relate in graph[key]:
dfs(relate,graph,path+[relate]) ## The backtracking of recursive functions is used here
dfs(0,graph,[0])
return ans
One has n A directed graph of nodes , Node press 0 To n - 1 Number . The figure consists of a Index from 0 Start Of 2D An array of integers graph Express , graph[i] Is associated with the node i Integer array of adjacent nodes , This means that the slave node i To graph[i] Each node in the has an edge .
If a node has no connected directed edge , Then it is Terminal nodes . If it's not out there , Then the node is the terminal node . If all possible paths from this node lead to Terminal nodes , Then the node is Security nodes .
Returns a list consisting of all Security nodes As an array of answers . The elements in the answer array should be pressed Ascending array .
Input ：graph = [[1,2],[2,3],[5],[0],[5],[],[]]
Output ：[2,4,5,6]
explain ： The schematic diagram is shown above .
node 5 And nodes 6 Is the terminal node , Because they don't come out .
From the node 2、4、5 and 6 All paths from the start point to the node 5 or 6 .
class Solution(object):
def eventualSafeNodes(self, graph):
""" :type graph: List[List[int]] :rtype: List[int] """
# Solution 1 ： Depth-first search + Tri-colour marking
# The important thing is to understand the meaning of the question , The safe state of this question actually refers to i Traverse for the starting point , Traverse nodes that do not form a ring
# Because as long as it doesn't form a ring , Can finally point to the terminal node
# Search with depth first + Tricolor marks can be obtained i As a mark of whether the starting point is looped
# n = len(graph)
# color = [0] * n # 0 Hang in the air 1 It's going on 2 Completed
# def safe(x):
# if color[x] > 0:
# return color[x] == 2
# color[x] = 1 ## If you order x
# for y in graph[x]:
# if not safe(y):
# return False
# color[x] = 2
# # If dfs After traversing, it doesn't return , It means that the point is not in the ring , It belongs to the security node , Modify the status and return to True
# return True
# return [i for i in range(n) if safe(i)]
# Solution 2 ： Reverse image + A topological sort
# This question graph Adjacency table , No need to rebuild
# If all possible paths from this node lead to Terminal nodes , Then the node is Security nodes .
# It is necessary to calculate the output of each node , The degree of 0 Is the terminal node
# If you make an inverse graph , That is, the degree of penetration is 0 Is the terminal node , And the final penetration can be 0 The node of
n=len(graph)
indeg=[0 for _ in range(n)]
adj=[[] for _ in range(n)]
for x,ys in enumerate(graph): #graph:x Point to y
for y in ys:
adj[y].append(x) #adj:y Point to x
indeg[x]+=1
# Now the degree of penetration is 0 The point of
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 # There are two ways to return results , One is to directly define a res Save the result , However, the results are required to be arranged in positive order , It also needs to be res.sort() It will increase the time complexity
return [i for i, d in enumerate(indeg) if d == 0] # A direct use indeg, If indeg[i]==0, Return its subscript
