我正在学习解决leetcode中的拓扑排序问题
There are a total of n courses you have to take, labeled from
0
ton-1
.Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair:
[0,1]
Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?
Example 1:
Input: 2, [[1,0]] Output: true Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.
Example 2:
Input: 2, [[1,0],[0,1]] Output: false Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.
Note:
- The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
- You may assume that there are no duplicate edges in the input prerequisites.
我在讨论区阅读了以下拓扑排序解决方案
class Solution5:
def canFinish(self,numCourses, prerequirements):
"""
:type numCourse: int
:type prerequirements: List[List[int]]
:rtype:bool
"""
if not prerequirements: return True
count = []
in_degrees = defaultdict(int)
graph = defaultdict(list)
for u, v in prerequirements:
graph[v].append(u)
in_degrees[u] += 1 #Confused here
queue = [u for u in graph if in_degrees[u]==0]
while queue:
s = queue.pop()
count.append(s)
for v in graph(s):
in_degrees[v] -= 1
if in_degrees[v] ==0:
queue.append(v)
#check there exist a circle
for u in in_degrees:
if in_degrees[u]:
return False
return True
我对in_degrees[u] += 1
感到困惑
for u, v in prerequirements:
graph[v].append(u)
in_degrees[u] += 1 #Confused here
对于有向边(u,v),u----->;节点u有一个outdegree,而节点v有一个indegree
所以我认为in_degrees[u] += 1
应该改成in_degrees[v] += 1
因为如果存在(u,v),那么v至少有一个传入事件和一个indegree
In Degree: This is applicable only for directed graph. This represents the number of edges incoming to a vertex.
然而,最初的解决方案是有效的
我的理解有什么问题
看看上面的那条线
graph[v].append(u)
。这些边实际上与您的假设和输入格式的方向相反。这是因为对于拓扑排序,我们希望没有依赖项/传入边的东西最终位于结果顺序的前面,因此我们根据解释“is requirement for”而不是“requires”来引导边。输入对(0,1)意味着0需要1,所以在图中我们画了一条有向边(1,0),这样在我们的排序中1可以先于0。因此,0从考虑这一对中获得了独立性相关问题 更多 >
编程相关推荐