当前位置：首页 > news >正文

华为C++笔试--拓扑排序

news 来源：原创 2024/5/20 20:50:23

题目：

某部门在开发一个代码分析工具，需要分析代码模块之间的依赖关系，用来确定模块的初始化顺序、是否有循环依赖等问题。“批量初始化”是指次可以初始化一个或多个模块。例如模块1依赖模块2模块3也依赖模块2，但模块1和3没有依赖关系。则必须先“批量初始化“模块2，再”批量初始化”模块1和3。现给定一组模块间的依赖关系，请计算需要”批量初始化”的次数。
每一个模块，包含自己的id，和其父亲id。

时间限制: C/C++ 1000ms,其他语言: 2000ms
内存限制:C/C++ 256MB,其他语言:512MB

输入
(1)第1行只有一个数字,表示模块总数N。
(2)随后的N行依次表示模块1到N的依赖数据。每行的第1个数据表示依赖的模块数量 (不会超过N)，之后的数字表示当前模块依赖的模块ID序列，该序列不会重复出现相同的数字，模块ID的取值一定在[1,N]之内。
(3)模块总数N取值范围 1<=N<=1000。
(4)每一行里面的数字按1个空格分隔

输出
输出”批量初始化次数”；
若有循环依赖无法完成初始化，则输出-1；

样例
输入:
5
3 2 3 4
1 5
1 5
1 5
0
输出: 3
解释:共5个模块。模块1依赖模块2、3、4;模块2依赖模块5;模块3依赖模块5;模块4依赖模块5;模块5没有依赖任何模块批量初始化顺序为(5)-2,3,4-1,共需”批量初始化"3次。

解题思路：

我们的目标是计算出“批量初始化”的次数，即我们需要找出所有模块的依赖关系，然后确定哪些模块可以同时初始化，最后计算出需要初始化的次数。

1、读取模块总数 N： 这是问题的第一行输入。
2、读取依赖关系： 接下来的 N 行中，每行表示一个模块及其依赖的模块ID。
3、构建依赖图： 使用一个图（可以用邻接表表示）来存储模块之间的依赖关系。
4、计算入度： 对于图中的每个节点，计算其入度（即有多少模块依赖于它）。
5、拓扑排序： 使用入度为0的节点开始，进行拓扑排序。在排序过程中，每次选择一个入度为0的节点，将其加入结果列表，并减少其所有依赖节点的入度。
6、检查循环依赖： 如果在拓扑排序过程中发现有节点的入度仍然不为0，说明存在循环依赖，无法完成初始化，返回-1。
7、计算批量初始化次数： 如果所有节点都被加入结果列表，那么返回结果列表的长度（即批量初始化的次数）。

C++程序实现

#include <iostream>
#include <vector>
#include <queue>using namespace std;// 添加依赖关系
void addEdge(vector<vector<int>> &graph, int u, int v) {graph[u].push_back(v);
}// 计算批量初始化次数
int calculateBatchInitializeCount(vector<vector<int>> &dependencies, int N) {// 构建有向图vector<vector<int>> graph(N + 1);for (int i = 0; i < dependencies.size(); ++i) {int module = dependencies[i][0];for (int j = 1; j < dependencies[i].size(); ++j) {addEdge(graph, module, dependencies[i][j]);}}// 计算每个模块的入度vector<int> inDegree(N + 1, 0);for (int i = 0; i < N; ++i) {for (int j : graph[i + 1]) {inDegree[j]++;}}// 找到所有入度为0的模块queue<int> queue;for (int i = 1; i <= N; ++i) {if (inDegree[i] == 0) {queue.push(i);}}int batchInitializeCount = 0;while (!queue.empty()) {int module = queue.front();queue.pop();batchInitializeCount++;// 减少其所有依赖模块的入度for (int child : graph[module]) {inDegree[child]--;if (inDegree[child] == 0) {queue.push(child);}}}// 检查是否所有模块都被初始化for (int i = 1; i <= N; ++i) {if (inDegree[i] > 0) {return -1;  // 存在循环依赖，无法完成初始化}}return batchInitializeCount;
}int main() {int N;cin >> N;vector<vector<int>> dependencies(N);for (int i = 0; i < N; ++i) {int count;cin >> count;dependencies[i].push_back(count);for (int j = 0; j < count; ++j) {int parent;cin >> parent;dependencies[i].push_back(parent);}}int result = calculateBatchInitializeCount(dependencies, N);cout << float(result) << endl;return 0;
}

这个程序按照解题思路执行，首先读取模块总数和依赖关系，然后构建依赖图并计算入度，接着找到所有入度为0的模块并进行拓扑排序。在排序过程中，每次选择一个入度为0的模块，将其加入结果列表，并减少其所有依赖节点的入度。如果所有节点都被加入结果列表，那么返回结果列表的长度，即批量初始化的次数。如果在这个过程中发现有节点的入度仍然不为0，说明存在循环依赖，无法完成初始化，返回-1。

程序的关键在于正确地构建依赖图和进行拓扑排序。使用一个图（邻接表形式）来表示模块之间的依赖关系，使用一个队列来存储入度为0的模块，并按照入度从0到N的顺序进行排序。

注意事项

1.程序中使用了vector和queue来自动管理内存和执行排序操作。
2.calculateBatchInitializeCount函数负责计算批量初始化次数，如果存在循环依赖，它将返回-1。
3.在主函数main中，程序读取输入并调用calculateBatchInitializeCount函数来获取结果。
4.程序输出的是一个单精度整数，因此使用float(result)来确保以浮点数的形式输出。