华为 2023年4月19日 实习 机试第一题——批量初始化次数

某部门在开发一个代码分析工具，需要分析模块之间的依赖关系，用来确定模块的初始化顺序，是否有循环依期等问题。

“批量初始化” 是指一次可以初始化一个或多个模块。

例如 模块 1 依赖模块 2， 模块 3 也依赖模块 2， 但模块 1 和 3 没有依赖关系， 则必须先 “批量初始化” 模块 2，再 “批量初始化” 模块 1 和 3。

现给定一组模块间的依赖关系，请计算需要 “批量初始化” 的次数。

输入

1. 第 1 行只有一个数字.表示模块总数 NNN。
2. 随后的 NNN 行依次表示模块 1 到 NNN 的依赖数据。每行的第 1 个数表示依赖的模块数量(不会超过 NNN)，之后的数字表示当前模块依赖的 ID 序列。该序列不会重复出现相同的数字，模块 ID 的取值定在 [1,N] 之内。
3. 模块总数 NNN 取值范围 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 次

示例二

输入

3
1 2
1 3
1 1

输出

-1

说明

存在循环依赖，无法完成初始化，返回-1

解法

每次选择出度为0的资源进行初始化，计算总共有多少躺，如果某一躺初始化的资源数为0（即找不到出度为0的资源，那么就存在环，输出-1返回）

#include <iostream>
#include <vector>
using namespace std;

int main() {
    // 思路：每次迭代找出出度为0的资源，删除后再次查找出度为0的资源
    int n;
    cin>>n;
    vector<pair<int, bool>> dg(n, {0, false});   // 出度，是否被加载
    vector<vector<bool>> map(n, vector<bool>(n, false));
    int num;
    for (int i = 0; i < n; i++) {
        cin>>dg[i].first;
        for (int j = 0; j < dg[i].first; j++) {
            cin>>num;
            map[i][num - 1] = true;
        }
    }
    int cnt = n;
    int times = 0;
    while (cnt > 0) {
        // 找出出度为0的资源
        int del = 0;
        for (int i = 0; i < n; i++) {
            if (!dg[i].second && dg[i].first == 0) {
                // 将其从其他资源的出边删除
                dg[i].second = true;
                for (int j = 0; j < n; j++) {
                    if (map[j][i]) {
                        map[j][i] = false;
                        dg[j].first--;
                    }
                }
                del++;
                cnt--;
            }
        }
        if (del > 0) {
            times++;
        } else if (del == 0) {
            cout<<-1<<endl;
            return 0;
        }
    }
    cout<<times<<endl;
    return 0;
}