题面描述:

题目要求计算给定模块间的依赖关系所需的最少“批量构建”次数，输入由一个正整数 $N$ 表示模块总数，接下来的 $N$ 行描述每个模块的依赖关系，第一项是该模块依赖的模块数量，后续项是具体的模块编号。如果存在循环依赖导致无法完成构建，则输出 $-1$；如果没有，则输出所需的最少“批量构建”次数。例如，对于输入 5\n3 2 3 4\n1 5\n1 5\n1 5\n0，输出应为 3；对于输入 3\n1 2\n1 3\n1 1，输出应为 -1。

思路

可以使用拓扑排序来解决。

将每个模块看作图中的一个节点，如果模块 $A$ 依赖模块 $B$，则在图中添加一条从 $B$ 指向 $A$ 的有向边。

用 $cnt$ 来记录节点入队的次数，$dep[i]$ 表示节点 $i$ 的深度，记所有初始入度为 0 的点深度为 0。

如果最后 $cnt$ 的数量不等于 $n$ ，则表示不能循环依赖，否则最后的答案为 $max(dep[i])$ $(1 \le i \le n)$

主要步骤

1. 建图：

   • 使用邻接表 graph 存储模块之间的依赖关系。
   • 使用数组 d 来记录每个模块的入度（即有多少模块依赖于该模块）。如果一个模块的入度为 0，表示它可以独立构建。

2. 初始化：

   • 遍历输入数据，构建邻接表和入度数组。对于每个模块 $i$，如果它依赖于模块 $x$，则在 graph[x] 中添加一条从 $x$ 到 $i$ 的边，并将模块 $i$ 的入度加 1。

3. 拓扑排序：

   • 使用双端队列 q 存储当前所有入度为 0 的模块。初始化时，将所有入度为 0 的模块加入队列。
   • 记录处理的节点数量 cnt 和每个节点的深度 dep。深度代表在构建过程中当前模块需要被构建的层级。

4. 处理节点：

   • 通过队列逐个处理模块。每当从队列中取出一个节点时，将 cnt 增加 1，并遍历它的所有邻接节点，将邻接节点的入度减 1。
   • 如果邻接节点的入度减到 0，则将其加入队列，并更新它的深度为当前节点深度加 1。

5. 检测循环依赖：

   • 如果 cnt 的数量不等于模块总数 $n$，则说明存在循环依赖，输出 -1。
   • 否则，输出 dep 数组中的最大值加 1（因为深度是从 0 开始的，代表的构建层级）。

AC代码

• Python

from collections import deque

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    # 获取节点数 n
    idx = 0
    n = int(data[idx])
    idx += 1
    
    # 初始化入度数组 d 和邻接表 graph
    d = [0] * (n + 1)
    graph = [[] for _ in range(n + 1)]
    
    # 构建邻接表和入度数组
    for i in range(1, n + 1):
        k = int(data[idx])
        idx += 1
        while k > 0:
            k -= 1
            x = int(data[idx])
            idx += 1
            graph[x].append(i)
            d[i] += 1
    
    # 执行拓扑排序
    q = deque()
    for i in range(1, n + 1):
        # 将所有入度为0的节点加入队列
        if d[i] == 0:
            q.append(i)
    cnt = 0 # 记录节点入队次数
    dep = [0] * (n + 1) # 记录每个节点的深度
    while q:
        # 从队列中取出一个节点
        t = q.popleft()
        cnt += 1 
        # 遍历该节点的所有邻接节点
        for i in graph[t]:
            # 将邻接节点的入度减1
            d[i] -= 1
            # 如果邻接节点的入度变为0,则加入队列
            if d[i] == 0:
                q.append(i)
                # 更新邻接节点的深度
                dep[i] = dep[t] + 1
    
    # 判断是否存在循环依赖
    if cnt != n: 
        print(-1) 
    else:
        print(max(dep) + 1)

if __name__ == "__main__":
    main()

• CPP

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int main() {
    // 获取节点数 n
    int n;
    cin >> n;
    
    // 初始化入度数组 d 和邻接表 graph
    vector<int> d(n + 1, 0);
    vector<vector<int>> graph(n + 1);
    
    // 构建邻接表和入度数组
    for (int i = 1; i <= n; ++i) {
        int k;
        cin >> k;
        while (k > 0) {
            --k;
            int x;
            cin >> x;
            graph[x].push_back(i);
            d[i]++;
        }
    }
    
    // 执行拓扑排序
    deque<int> q;
    for (int i = 1; i <= n; ++i) {
        // 将所有入度为0的节点加入队列
        if (d[i] == 0) {
            q.push_back(i);
        }
    }

    int cnt = 0; // 记录节点入队次数
    vector<int> dep(n + 1, 0); // 记录每个节点的深度
    while (!q.empty()) {
        // 从队列中取出一个节点
        int t = q.front();
        q.pop_front();
        cnt++;
        // 遍历该节点的所有邻接节点
        for (int i : graph[t]) {
            // 将邻接节点的入度减1
            d[i]--;
            // 如果邻接节点的入度变为0,则加入队列
            if (d[i] == 0) {
                q.push_back(i);
                // 更新邻接节点的深度
                dep[i] = dep[t] + 1;
            }
        }
    }
    
    // 判断是否存在循环依赖
    if (cnt != n) {
        cout << -1 << endl;
    } else {
        cout << *max_element(dep.begin(), dep.end()) + 1 << endl;
    }
    
    return 0;
}

• Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // 创建 Scanner 对象读取输入
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        // 初始化入度数组 d 和邻接表 graph
        int[] d = new int[n + 1];
        List<Integer>[] graph = new ArrayList[n + 1];
        
        // 构建邻接表和入度数组
        for (int i = 1; i <= n; i++) {
            graph[i] = new ArrayList<>();
        }
        
        for (int i = 1; i <= n; i++) {
            int k = sc.nextInt();
            while (k > 0) {
                k--;
                int x = sc.nextInt();
                graph[x].add(i);
                d[i]++;
            }
        }
        
        // 执行拓扑排序
        Deque<Integer> q = new ArrayDeque<>();
        for (int i = 1; i <= n; i++) {
            // 将所有入度为0的节点加入队列
            if (d[i] == 0) {
                q.add(i);
            }
        }

        int cnt = 0; // 记录节点入队次数
        int[] dep = new int[n + 1]; // 记录每个节点的深度
        while (!q.isEmpty()) {
            // 从队列中取出一个节点
            int t = q.poll();
            cnt++;
            // 遍历该节点的所有邻接节点
            for (int i : graph[t]) {
                // 将邻接节点的入度减1
                d[i]--;
                // 如果邻接节点的入度变为0,则加入队列
                if (d[i] == 0) {
                    q.add(i);
                    // 更新邻接节点的深度
                    dep[i] = dep[t] + 1;
                }
            }
        }
        
        // 判断是否存在循环依赖
        if (cnt != n) {
            System.out.println(-1);
        } else {
            System.out.println(Arrays.stream(dep).max().getAsInt() + 1);
        }
        
        // 关闭 Scanner 对象
        sc.close();
    }
}

javascript

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

(async function () {
    let n = parseInt(await readline()); // 读取 n

    let d = Array(n + 1).fill(0); // 入度数组
    let graph = Array.from({ length: n + 1 }, () => []); // 邻接表

    // 读取邻接表
    for (let i = 1; i <= n; i++) {
        let input = (await readline()).split(" ").map(Number);
        let k = input[0]; // 读取依赖数量
        for (let j = 1; j <= k; j++) {
            let x = input[j];
            graph[x].push(i); // 建立邻接关系
            d[i]++; // 计算入度
        }
    }

    let queue = []; // 拓扑排序队列
    for (let i = 1; i <= n; i++) {
        if (d[i] === 0) {
            queue.push(i); // 入度为 0 的节点入队
        }
    }

    let cnt = 0; // 记录节点入队次数
    let dep = Array(n + 1).fill(0); // 记录每个节点的深度

    while (queue.length > 0) {
        let t = queue.shift(); // 取出队列头部元素
        cnt++;
        for (let i of graph[t]) {
            d[i]--; // 入度减少
            if (d[i] === 0) {
                queue.push(i);
                dep[i] = dep[t] + 1; // 更新深度
            }
        }
    }

    // 判断是否存在循环依赖
    if (cnt !== n) {
        console.log(-1);
    } else {
        console.log(Math.max(...dep) + 1);
    }

    rl.close();
})();

题目描述

小明是一名资深软件工程师,他正在开发一个代码依赖分析工具。这个工具需要分析软件模块之间的依赖关系,用来优化代码的编译和构建过程。

在该工具中,"批量构建"是指将多个没有依赖关系的模块一次性进行编译和构建。例如,如果模块 $A$ 依赖模块 $B$ 和 $C$,模块 $D$ 依赖模块 $C$,但模块 $B$ 和 $D$ 之间没有依赖关系,则需要先"批量构建"模块 $B$ 和 $C$,再分别构建模块 $A$ 和 $D$。

现在,给定一组模块间的依赖关系,请你帮助小明计算需要"批量构建"的最少次数。

输入格式

第一行只有一个正整数 $N$,表示模块总数。

随后的 $N$ 行依次表示模块 $1$ 到 $N$ 的依赖关系。每行的第一个数据 $K_i$ 表示模块 $i$ 依赖的模块数量,之后跟着 $K_i$ 个整数,表示模块 $i$ 依赖的模块编号。模块编号的取值范围为 $[1,N]$,且每行中的模块编号各不相同。

输出格式

输出"批量构建"的最少次数。若存在循环依赖导致无法完成构建,则输出 $-1$。

样例输入1

5
3 2 3 4
1 5
1 5
1 5
0

样例输出1

3

样例输入2

3
1 2
1 3
1 1

样例输出2

-1

评测数据与规模

• $1 \leq N \leq 1000$
• $0 \leq K_i < N$
• 输入数据保证模块编号在 $[1,N]$ 范围内,且不存在自依赖的情况。