首页 > 试题广场 >

编译依赖问题

[编程题]编译依赖问题

热度指数：4058 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

一个完整的软件项目往往会包含很多由代码和文档组成的源文件。编译器在编译整个项目的时候，可能需要按照依赖关系来依次编译每个源文件。比如，A.cpp 依赖 B.cpp，那么在编译的时候，编译器需要先编译 B.cpp，才能再编译 A.cpp。假设现有 0，1，2，3 四个文件，0号文件依赖1号文件，1号文件依赖2号文件，3号文件依赖1号文件，则源文件的编译顺序为 2,1,0,3 或 2,1,3,0。现给出文件依赖关系，如 1,2,-1,1，表示0号文件依赖1号文件，1号文件依赖2号文件，2号文件没有依赖，3号文件依赖1号文件。请补充完整程序，返回正确的编译顺序。注意如有同时可以编译多个文件的情况，按数字升序返回一种情况即可，比如前述案例输出为：2,1,0,3

示例1

输入

"1,2,-1,1"

输出

"2,1,0,3"

备注:

-1 表示当前文件没有依赖，输出结果用英文逗号分隔。暂不考虑一个文件依赖多个文件的情况。

算法知识视频讲解

Python

牛客589187471号

python3解法：拓扑排序

import heapq
class Solution:
    def compileSeq(self , input ):
        # write code here
        nums = [int(x) for x in input.split(",")]
        n = len(nums)
        in_degree = [0] * n
        relation = [set() for _ in range(n)]
        res = []
        que = []
        
        for i in range(n):
            if nums[i] != -1:
                in_degree[i] += 1
                relation[nums[i]].add(i)
        
        for i in range(n):
            if in_degree[i] == 0:
                que.append(i)
        
        while que:
            cur = que[0]
            que = que[1:]
            res.append(cur)
            for idx in relation[cur]:
                in_degree[idx] -= 1
                if in_degree[idx] == 0:
                    heapq.heappush(que, idx)
        string = ",".join([str(x) for x in res])
        return string

发表于 2021-04-09 20:26:43 回复(1)