讨论/《深度优先搜索》 - 例题:课程表 II/
《深度优先搜索》 - 例题:课程表 II
共 3 个回复

拓扑排序

class Solution:
    def findOrder(self, n: int, ps: List[List[int]]) -> List[int]:
        ins = [0] * n
        ous = collections.defaultdict(list)
        for cur,pre in ps:
            ins[cur] += 1
            ous[pre].append(cur)
        res = list(filter(lambda x:ins[x]==0, range(n)))
        q = collections.deque(res)
        while q:
            pre = q.popleft()
            for cur in ous[pre]:
                ins[cur] -= 1
                if not ins[cur]:
                    q.append(cur)
                    res.append(cur)
        return res if len(res) == n else []
1

维哥好久不见,最近换工作了没

「拓扑排序」用「广度优先遍历」更常见,棒!