1 solutions

  • 0
    @ 9 months ago

    题目大意

    塔子哥决定开发一个工具来分析模块之间的依赖关系,计算引擎模块初始化的次数。如果模块之间存在循环依赖,则无法完成初始化,工具应该输出 -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
    
    • 1

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

    Information

    ID
    13
    Time
    1000ms
    Memory
    256MiB
    Difficulty
    7
    Tags
    # Submissions
    108
    Accepted
    55
    Uploaded By