心路历程:
第一反应是用并查集求解,但是写完之后发现逻辑错误,因为要求的是判断有向图是否有环的问题,而并查集只能解决无向图成环的问题。
第二反应是用链表来解决问题,以此转化为判断链表是否成环,因为链表是有方向的,后来发现还是不行,因为链表只有一个或者两个指针,但是题目中其实一个课程可能有多个指针。
这道题的本质是一个构建有向图,然后判断有向图中是否有环的问题,之前没有遇到过这类问题,而且感觉这种类型应该是一类题,于是上网搜索了答案。
网上有两类做法,分别是拓扑排序和DFS。
考虑基于拓扑排序的思路:
考虑基于DFS的思想来做:1、利用逆邻接集合建图 2、递归遍历每一个结点
注意的点:
1、书写并查集时注意find函数要return **self.find(self.father[x])**而不是self.father(x) or self.find(x)
2、链表的指针数量是一个或者两个有限的
3、有向图的成环问题首选拓扑排序+BFS,核心在于每次把入度为0的点加入队列,并且把其子节点入度减一。
解法一:拓扑排序+BFS判断有向图成环:
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
if len(prerequisites) == 0: return True
# 入度数组,记录了有几个father
in_degrees = [0 for _ in range(numCourses)]
adj = [set() for _ in range(numCourses)]
# 利用邻接表建图
for child, father in prerequisites:
in_degrees[child] += 1
adj[father].add(child)
# 把所有入度为 0 的结点加入到一个队列中
queue = []
for i in range(numCourses):
if in_degrees[i] == 0: queue.append(i)
counter = 0
while queue:
temp = queue.pop(0)
counter += 1
for child in adj[temp]:
in_degrees[child] -= 1 # 把这个结点的所有后继结点的入度减去 1,如果发现入度为 0 ,就马上添加到队列中
if in_degrees[child] == 0:
queue.append(child)
return counter == numCourses # 不相等的话代表原图中有环,使得去除入度为0的结点时无法去除
解法二:逆邻接集合的DFS
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
if len(prerequisites) == 0: return True
node_state = [0 for _ in range(numCourses)] # 0 1 2代表三种结点状态
inverse_adj = [set() for _ in range(numCourses)]
for child, father in prerequisites:
inverse_adj[child].add(father) # 建图,记录每个结点的前驱结点
def dfs(nodei):
nonlocal inverse_adj, node_state
if node_state[nodei] == 2: return True # 有环
if node_state[nodei] == 1: return False
node_state[nodei] = 2
for each_father in inverse_adj[nodei]:
if dfs(each_father): return True
node_state[nodei] = 1
return False
for i in range(numCourses):
if dfs(i): return False
return True
错误做法一:并查集:
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
# 并查集成环的题;有向图其实不方便用并查集
uf = UF(numCourses)
for eve in prerequisites:
res = uf.union(eve[0], eve[1])
if res: return False
return True
class UF:
def __init__(self, n):
self.father = list(range(n))
def find(self, x):
if x == self.father[x]: return x
return self.find(self.father[x]) # 忘了递归了...
def union(self, x, y):
fx, fy = self.find(x), self.find(y)
print(x, y, fx, fy)
if fx == fy: # 不止需要成环
if x == fy: return True # 这样判断也不对
self.father[fx] = fy # y是父亲
return False
错误解法二:链表成环:
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
# 这道题可以用链表成环的思路去解决
# 先构建链表
visited = {}
for eve in prerequisites:
child, father = eve[0], eve[1]
if child not in visited: visited[child] = Link(child, None)
if father not in visited: visited[father] = Link(father, None)
visited[child].next = visited[father]
# 从任意一个链表结点出发都不应该有环
print(visited)
for i in visited.keys(): # 从i出发遍历
visited2 = set()
t = visited[i]
while t:
if t.val not in visited2: visited2.add(t.val)
else: return False
t = t.next
return True
class Link:
def __init__(self, val, next):
self.val = val
self.next = next