讨论/《深度优先搜索》 - 练习:平行课程/
《深度优先搜索》 - 练习:平行课程
共 1 个回复
class Solution:
    def minimumSemesters(self, N: int, ps: List[List[int]]) -> int:
        ins = [0] * N
        ous = collections.defaultdict(list)
        for cur,pre in ps:
            ins[cur-1] += 1
            ous[pre-1].append(cur-1)
        res = list(filter(lambda x:ins[x]==0, range(N)))
        q = collections.deque(res)
        cnt = len(res)
        deep = 0
        while q :
            pre = q.popleft()
            for cur in ous[pre]:
                ins[cur] -= 1
                if not ins[cur]:
                    q.append(cur)
                    res.append(cur)
            cnt -= 1
            if not cnt:
                deep += 1
                cnt = len(q)
        return deep if len(res) == N else -1