讨论个看到过多次的面经题

qldx 发表于 2020-09-13 17:50:04
那如果是说有先后顺序的必须要先满足前面的，没有任何先决条件的都可以同时进行的话，那不就是210. Course Schedule II的普通拓扑排序了么？

210 是直接输出一整个 这个需要每一层分别输出 比如 层和层之间有先后关系

这个没关系，可以用bfs来进行，一层一层的更新

1.    
   
2. def findOrder(self, numCourses, prerequisites):
   
3.         """
   
4.         :type numCourses: int
   
5.         :type prerequisites: List[List[int]]
   
6.         :rtype: List[int]
   
7.         """
   
8.         indegree = dict()#每个课程依赖于哪些课程
   
9.         outdegree = dict()#每个课程决定哪些课程
   
10.         for i,j in prerequisites:
    
11.             if i not in indegree:
    
12.                 indegree[i] = set()#{2:{1}}
    
13.             indegree[i].add(j)
    
14.             if j not in outdegree:
    
15.                 outdegree[j] = set()# {1:{2}}
    
16.             outdegree[j].add(i)
    
17. 
    
18.         res = []
    
19.         level = [i for i in range(numCourses) if i not in indegree]
    
20.         res = [[i for i in range(numCourses) if i not in indegree]]
    
21.         while level:
    
22.             newlevel = []
    
23.             for i in level:
    
24.                 if i in outdegree:
    
25.                     for j in outdegree[i]:
    
26.                         indegree[j].remove(i)
    
27.                         if len(indegree[j])==0:
    
28.                             newlevel.append(j)
    
29.             level = newlevel
    
30.             res.append(level)
    
31.         return res
    

复制代码

qldx 发表于 2020-09-13 18:06:56
这个没关系，可以用bfs来进行，一层一层的更新
   
def findOrder(self, numCourses, prerequisites):

这个好像会有问题 比如 [ A, B] , [ A, C], [C, B] 如果先从a访问到B 就会把B放进第二层 但其实应该放进第三层

Smilenceyu 发表于 2020-9-14 09:16
这个好像会有问题 比如 [ A, B] , [ A, C], [C, B] 如果先从a访问到B 就会把B放进第二层 但其实应该放进第 ...

我感觉应该是可行的，这个算法我写过几次（不过由于题目有些许差异，上面那个代码返回的结果是反的），第一次把没有前提条件的放在level中，然后对level里的每个元素，去掉对应关系（比如你的这个例子，刚开始level=[A], 去掉[A,C]，[A,B] 之后，C的前提条件那里就是空的了，然后放进新的level里，但是B的前提条件还是有元素的，所以还得再进行一轮）

qldx 发表于 2020-09-13 18:37:46
我感觉应该是可行的，这个算法我写过几次（不过由于题目有些许差异，上面那个代码返回的结果是反的），第一次把没有前提条件的放在level中，然后对level里的每个元素，去掉对应关系（比如你的这个例子，刚

Ic 所以用kahns algorithm 的确是可以的 好像会比dfs方便一些