ID: 13

Difficulty: 7

题目内容

塔子哥是一名软件工程师，他正在为一家游戏公司开发一个新的3D引擎。这个引擎由多个模块组成，每个模块负责不同的功能，比如渲染、物理、音效、网络等。

为了提高性能和稳定性，塔子哥需要在游戏启动时初始化这些模块，但是有一个问题：不同的模块之间存在依赖关系，比如渲染模块依赖于物理模块，音效模块依赖于网络模块等。如果塔子哥不按照正确的顺序初始化这些模块，就会导致错误或崩溃。

为了解决以上问题，塔子哥决定开发一个代码分析工具，用来分析代码模块之间的依赖关系，用来确定模块的初始化顺序、是否有循环依赖等问题。

塔子哥的工具可以一次初始化一个或多个模块，只要它们之间没有依赖关系。他把这个过程称为引擎模块初始化。

现在，塔子哥已经得到了一组模块间的依赖关系，塔子哥需要计算需要引擎模块初始化的次数。

输入描述

输入第一行为一个整数 $n$ ，表示模块总数。

接下来的 $n$ 行依次表示模块 $1$ 到 $n$ 的依赖关系。

输入每行的第一个数为一个整数 $m$ ，表示依赖的模块数量(不会超过 $n$ )，之后的数字表示当前模块依赖的模块ID序列，该序列不会重复出现相同的数字，并且模块ID的取值一定在 $[1,n]$ 之内。

每一行里面的数字按一个空格分隔。

$1\le m\le n \le 1000$

输出描述

输出”批量初始化次数”。

若有循环依赖无法完成初始化，则输出 $-1$ 。

样例

样例一

输入

输出

样例解释

共 $5$ 个模块。

模块 $1$ 依赖模块 $2$ 、 $3$ 、 $4$ ；

模块 $2$ 依赖模块 $5$ ；

模块 $3$ 依款模块 $5$ ；

模块 $4$ 依赖模块 $5$ ；

模块 $5$ 没有依赖任何模块。

批量初始化顺序为 $\{5\}->\{2，3，4\}-> \{1\}$ ，共需”批量初始化” $3$ 次。

样例二

输入

输出

-1

样例解释

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

题目大意

塔子哥决定开发一个工具来分析模块之间的依赖关系，计算引擎模块初始化的次数。如果模块之间存在循环依赖，则无法完成初始化，工具应该输出 -1，表示初始化失败。

解题思路

这个问题可以抽象为拓扑排序的问题。如果模块之间没有循环依赖，我们可以通过拓扑排序确定模块初始化的顺序。如果存在循环依赖，意味着无法完成拓扑排序。

思路步骤

1.构建依赖图：

每个模块可以依赖其他模块，这可以通过有向图来表示，其中每个模块是一个节点，依赖关系是有向边。图的边从依赖的模块指向当前模块。例如，如果模块 A 依赖于模块 B，那么边应该从 B 指向 A。

2.计算入度：

入度表示每个节点（模块）有多少个依赖关系。我们需要计算每个模块的入度，即有多少个模块是当前模块的前置依赖。

3.拓扑排序：

使用拓扑排序算法（Kahn 算法），从入度为 0 的模块开始，每次移除一个模块，并减少它所依赖模块的入度。当某个模块的入度变为 0 时，意味着它的所有前置依赖都已经被初始化，可以安全初始化这个模块。记录执行的轮次，轮次代表每一批可以同时初始化的模块数。

4.检测循环依赖：

如果经过拓扑排序后，仍然存在某些模块没有被处理，说明存在循环依赖，输出 -1。

代码说明

1。初始化图和入度数组： 根据输入，构建每个模块的依赖关系，记录每个模块的入度。

2.处理入度为 0 的模块： 使用队列（或栈）存储所有入度为 0 的模块，开始拓扑排序。

3.拓扑排序：

每次从队列中取出一个入度为 0 的模块，处理它所依赖的模块（将其入度减 1）。如果某个模块的入度减为 0，将其加入队列。记录批次，每次从队列中取出模块时，都代表可以初始化这些模块。

4.检测是否存在循环依赖：

如果所有模块都被处理，输出批量初始化的轮次。如果有模块未被处理，输出 -1，表示存在循环依赖。

C++

解法1

#include<bits/stdc++.h>
using namespace std;
/*
	e: 邻接表，用于存储依赖关系
	d: 入度数组，表示每个节点的入度
	dp: 从任意源点到该节点的最长路径，表示每个模块初始化的批次
*/
vector<int> e[10005];  // 邻接表存储依赖关系
int d[10005], dp[10005];  // d存储入度，dp存储最早的初始化批次

int main() {
    // 读入模块数量，并建立依赖关系图
    int n;
    cin >> n;
    
    // 遍历每个模块，读取其依赖的模块并构建邻接表
    for (int i = 1; i <= n; i++) {
        int m;  // 当前模块的依赖数量
        cin >> m;
        
        // 读取当前模块的所有依赖模块
        for (int j = 1; j <= m; j++) {
            int x;
            cin >> x;  // 读取依赖的模块ID
            e[x].push_back(i);  // 在邻接表中记录依赖关系
            d[i]++;  // 当前模块的入度加1
        }
    }

    // 拓扑排序：处理入度为0的节点，表示可以直接初始化的模块
    queue<int> q;
    for (int i = 1; i <= n; i++) {
        if (d[i] == 0) {
            q.push(i);  // 将入度为0的模块加入队列
            dp[i] = 1;  // 初始化该模块，标记为第一批次
        }
    }

    // 拓扑排序处理
    while (!q.empty()) {
        int u = q.front();  // 取出队首元素
        q.pop();
        
        // 遍历当前模块所依赖的模块，并更新它们的批次
        for (auto v : e[u]) {
            dp[v] = max(dp[v], dp[u] + 1);  // 更新模块v的最早初始化批次
            d[v]--;  // 模块v的入度减1
            if (d[v] == 0) {  // 如果模块v的入度为0，表示可以初始化
                q.push(v);  // 加入队列等待处理
            }
        }
    }

    // 检查是否存在无法初始化的模块
    int mx = 0;
    for (int i = 1; i <= n; i++) {
        if (dp[i] == 0) {  // 如果某个模块的dp值为0，说明它无法初始化
            cout << -1 << endl;  // 输出-1表示存在循环依赖
            return 0;
        }
        mx = max(mx, dp[i]);  // 记录最大的批次数
    }

    // 输出最大批次数
    cout << mx << endl;
    return 0;
}

python

解法2

from collections import defaultdict, deque

# 读取模块数量
n = int(input())

# 使用默认字典存储每个模块的依赖关系
edges = defaultdict(list)
# 入度数组，in_[i] 表示模块 i 依赖的模块数量
in_ = [0] * (n + 1)

# 读取每个模块的依赖关系并构建图
for i in range(1, n + 1):
    # 读取当前模块的依赖信息
    temp = list(map(int, input().split()))
    # 从第二个数字开始，因为第一个数字是依赖数量
    for j in range(1, len(temp)):
        edges[temp[j]].append(i)  # 将依赖的模块加入邻接表
        in_[i] += 1  # 当前模块的入度加1

# 使用双端队列存储入度为0的模块（可以直接初始化）
queue = deque()
for i in range(1, n + 1):
    if in_[i] == 0:
        queue.append(i)  # 将入度为0的模块加入队列

# 如果没有任何模块可以初始化（存在循环依赖）
if not queue:
    print(-1, end=' ')
else:
    res = 0  # 记录批次初始化次数
    # 开始拓扑排序
    while queue:
        res += 1  # 每次处理队列中的模块即为一个批次
        n = len(queue)  # 当前批次模块数量
        # 遍历当前批次的所有模块
        for i in range(n):
            from_ = queue[0]  # 取出当前模块
            queue.popleft()  # 从队列中移除该模块
            # 遍历该模块的所有依赖模块
            for to_ in edges[from_]:
                in_[to_] -= 1  # 减少依赖模块的入度
                if in_[to_] == 0:  # 如果依赖模块的入度为0，表示可以初始化
                    queue.append(to_)  # 将该模块加入队列

    # 输出初始化所需的批次数
    print(res)

Java


import java.util.*;

public class Main {
    public void solution(){
        Scanner scanner = new Scanner(System.in);
        // 读取模块数量
        int n = scanner.nextInt();
        
        // inDegree数组存储每个模块的入度，表示模块有多少依赖项
        int[] inDegree = new int[n + 1];
        inDegree[0] = -1; // 下标0不用，设为-1避免干扰
        
        // outDegree数组使用ArrayList存储依赖关系的邻接表
        ArrayList<Integer>[] outDegree = new ArrayList[n + 1];
        
        // 读取依赖关系并更新入度和邻接表
        for(int i = 1; i <= n; ++i){
            int m = scanner.nextInt();  // 读取当前模块的依赖数量
            inDegree[i] += m;  // 当前模块的入度增加依赖数量
            
            // 读取依赖的模块，并将其加入邻接表
            for(int j = 0; j < m; ++j){
                int from = scanner.nextInt();  // 依赖的模块ID
                if(outDegree[from] == null)
                    outDegree[from] = new ArrayList<>();
                outDegree[from].add(i);  // 添加依赖关系，表示from指向当前模块
            }
        }
        scanner.close();  // 关闭输入流
        
        int res = 0;  // 记录批次初始化次数
        boolean check;  // 标志是否找到可以初始化的模块
        Queue<Integer> queue = new LinkedList<>();  // 队列，用于

Go

package main

import (
	"bufio"
	"fmt"
	"os"
)

const N = 1e3 + 10  // 定义最大模块数

var n, m int  // n 表示模块数量，m 表示每个模块的依赖数量

func main() {

	inDegrees := make([]int, N)     // 入度数组，记录每个模块的入度
	outDegrees := make([][]int, N)  // 出度数组，记录每个模块指向的依赖模块
	for i := range outDegrees {
		outDegrees[i] = make([]int, 0)  // 初始化每个模块的出度数组
	}

	in := bufio.NewReader(os.Stdin)  // 使用缓冲读取输入
	out := bufio.NewWriter(os.Stdout)  // 使用缓冲输出
	defer out.Flush()

	// 读取模块数量
	fmt.Fscan(in, &n)
	for i := 1; i <= n; i++ {
		fmt.Fscan(in, &m)  // 读取当前模块的依赖数量
		var id int
		inDegrees[i] = m  // 设置当前模块的入度为依赖数量
		for j := 0; j < m; j++ {
			fmt.Fscan(in, &id)  // 读取依赖的模块 ID
			outDegrees[id] = append(outDegrees[id], i)  // 将依赖关系加入邻接表
		}
	}

	queue := make([]int, 0)  // 初始化队列，用于拓扑排序
	for i := 1; i <= n; i++ {
		if inDegrees[i] == 0 {  // 将入度为 0 的模块加入队列
			queue = append(queue, i)
		}
	}
	if len(queue) == 0 {  // 如果队列为空，说明没有可以初始化的模块，可能有循环依赖
		fmt.Fprintln(out, -1)
		return
	}

	res, count := 0, 0  // res 记录批次数，count 记录已处理的模块数
	for len(queue) != 0 {
		size := len(queue)  // 当前批次模块数量
		count += size  // 累加处理的模块数量
		for i := 0; i < size; i++ {
			front := queue[0]  // 取出队列中的第一个模块
			queue = queue[1:]  // 队列出队
			for _, o := range outDegrees[front] {  // 遍历当前模块的所有依赖模块
				inDegrees[o]--  // 依赖模块的入度减 1
				if inDegrees[o] == 0 {  // 如果依赖模块的入度为 0，表示可以初始化
					queue = append(queue, o)  // 将其加入队列
				}
			}
		}
		res++  // 每处理完一批模块，批次数加 1
	}
	if count != n {  // 如果处理的模块数不等于总模块数，说明存在循环依赖
		fmt.Fprintln(out, -1)  // 输出 -1 表示无法完成初始化
		return
	}
	fmt.Fprintln(out, res)  // 输出批量初始化的次数
}

Js

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");
 
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});
 
const lines = [];
let n;
rl.on("line", (line) => {
  lines.push(line);
 
  if (lines.length == 1) {
    // 模块总数N
    n = lines[0] - 0;
  }
 
  if (n && lines.length == n + 1) {
    // 记录每个服务的入度值
    const inDegree = new Array(n + 1).fill(0);
    // 记录每个服务的所有后继服务
    const next = {};
 
    // 模块从1~N，这里将 i 作为模块标识
    for (let i = 1; i <= n; i++) {
      if (!next[i]) next[i] = [];
      const line = lines[i].split(" ").map(Number);
 
      // 统计入度值
      inDegree[i] = line[0];
 
      // 统计后继服务
      for (let j = 1; j < line.length; j++) {
        const pre = line[j];
        next[pre] ? next[pre].push(i) : (next[pre] = [i]);
      }
    }
 
    console.log(getResult(n, next, inDegree));
    lines.length = 0;
  }
});
 
/**
 *
 * @param {*} n 模块总数N
 * @param {*} next 记录每个服务的所有后继服务
 * @param {*} inDegree 记录每个服务的入度值
 * @returns 输出"批量初始化次数”。若有循环依赖无法完成初始化，则输出-1。
 */
function getResult(n, next, inDegree) {
  // queue记录入度值为0的点
  let queue = [];
  for (let i = 1; i <= n; i++) {
    if (inDegree[i] == 0) queue.push(i);
  }
 
  // ans记录"批量初始化次数”
  let ans = 0;
  // count记录已成功部署的模块，如果存在循环依赖，则最终count < n
  let count = 0;
 
  while (queue.length) {
    const newQueue = [];
 
    // 遍历入度值为0的模块
    for (let id of queue) {
      // 每遍历一个，就说明有一个模块部署成功
      count++;
      // 一个模块部署成功，则其后继模块的入度值需要减1
      for (let nextId of next[id]) {
        // 如果后继模块的入度值变为了0，则说明也可以部署了
        if (--inDegree[nextId] == 0) newQueue.push(nextId);
      }
    }
 
    // 这里使用newQueue的原因是，保证每次都能剥离一层入度为0的模块，这样会方便ans统计
    queue = newQueue;
    ans++;
  }
 
  // 如果存在循环依赖，则最后成功部署的模块数count < n
  return count == n ? ans : -1;
}
// by sunde

#P1573. 2023.04.26-暑期实习-第一题-引擎模块初始化

2023.04.26-暑期实习-第一题-引擎模块初始化