（新卷）产品模块算法检验（Java、Js、c\c++、python）-育师

产品模块算法检验

在产品配置中，一个配置产品是由多个产品模块(CM)构成，每个CM有自身的算法，且模块间可能存在算法依赖。例如电脑产品是由主板、CPU日、显卡等CM构成。CPU模块(CM1)算法依赖主板模块(CM2)算法，记作CM2<-CM1,算法引擎会通过算法依赖确保此前后CM执行的顺序。如果存在模块算法循环依赖的场景，那么算法引擎会报警。

输入描述 输入的第一行为模块列表，例如CM2，CM3，CM4; 输入的第二行为依赖情况,例如CM3<-CM2 输出描述 计算出循环依赖的CM数量 示例1： 输入： CM1,CM2,CM3,CM4,CM5,CM6 CM5<-CM3,CM4<-CM5,CM6<-CM4,CM6<-CM1,CM5<-CM6 输出： 3 示例2： 输入： CM1,CM2,CM3,CM4,CM5,CM6 CM5<-CM3,CM3<-CM6,CM6<-CM4,CM3<-CM4,CM4<-CM1 输出： 0

问题分析

该问题需要检测模块间的循环依赖关系，并计算参与循环依赖的模块数量。可以通过构建有向图并检测图中是否存在环来解决。

解决思路

构建有向图：将每个模块表示为图的节点，依赖关系表示为有向边（如CM3<-CM2表示从CM2指向CM3的边）。
检测环：使用深度优先搜索（DFS）或拓扑排序来检测图中是否存在环。
统计环中的节点：如果存在环，统计环中涉及的模块数量。

算法实现

以下是基于拓扑排序的实现方法：

每种语言实现逻辑一致，仅语法和数据结构差异。

计算每个节点的入度（被依赖的次数）。
将入度为0的节点加入队列，进行拓扑排序。
若最终排序的节点数不等于总节点数，则存在环。
python实现

from collections import defaultdict, deque def count_cyclic_dependencies(modules, dependencies): graph = defaultdict(list) in_degree = defaultdict(int) module_set = set(modules) # 初始化入度为0 for module in module_set: in_degree[module] = 0 # 构建图和入度 for dep in dependencies: dependent, dependee = dep.split('<-') graph[dependee].append(dependent) in_degree[dependent] += 1 # 拓扑排序 queue = deque() for module in module_set: if in_degree[module] == 0: queue.append(module) topo_order = [] while queue: node = queue.popleft() topo_order.append(node) for neighbor in graph[node]: in_degree[neighbor] -= 1 if in_degree[neighbor] == 0: queue.append(neighbor) # 检查是否存在环 if len(topo_order) == len(module_set): return 0 else: # 统计环中的节点数 # 通过反向遍历未排序的节点 cyclic_nodes = module_set - set(topo_order) return len(cyclic_nodes) # 示例1 modules = ['CM1', 'CM2', 'CM3', 'CM4', 'CM5', 'CM6'] dependencies = ['CM5<-CM3', 'CM4<-CM5', 'CM6<-CM4', 'CM6<-CM1', 'CM5<-CM6'] print(count_cyclic_dependencies(modules, dependencies)) # 输出3 # 示例2 modules = ['CM1', 'CM2', 'CM3', 'CM4', 'CM5', 'CM6'] dependencies = ['CM5<-CM3', 'CM3<-CM6', 'CM6<-CM4', 'CM3<-CM4', 'CM4<-CM1'] print(count_cyclic_dependencies(modules, dependencies)) # 输出0

Java实现

import java.util.*; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); String[] modules = scanner.nextLine().split(","); String[] dependencies = scanner.nextLine().split(","); Map<String, List<String>> graph = new HashMap<>(); for (String module : modules) { graph.put(module.trim(), new ArrayList<>()); } for (String dep : dependencies) { String[] parts = dep.trim().split("<-"); String dependent = parts[0].trim(); String dependency = parts[1].trim(); graph.get(dependency).add(dependent); } Set<String> visited = new HashSet<>(); Set<String> recursionStack = new HashSet<>(); List<String> cycleNodes = new ArrayList<>(); for (String module : modules) { if (detectCycle(module, graph, visited, recursionStack, cycleNodes)) { break; } } System.out.println(cycleNodes.size()); } private static boolean detectCycle(String module, Map<String, List<String>> graph, Set<String> visited, Set<String> recursionStack, List<String> cycleNodes) { if (recursionStack.contains(module)) { cycleNodes.add(module); return true; } if (visited.contains(module)) { return false; } visited.add(module); recursionStack.add(module); for (String neighbor : graph.get(module)) { if (detectCycle(neighbor, graph, visited, recursionStack, cycleNodes)) { if (!cycleNodes.contains(module)) { cycleNodes.add(module); } return true; } } recursionStack.remove(module); return false; } }

C++实现

#include <iostream> #include <vector> #include <unordered_map> #include <unordered_set> #include <sstream> using namespace std; bool detectCycle(const string& module, unordered_map<string, vector<string>>& graph, unordered_set<string>& visited, unordered_set<string>& recursionStack, vector<string>& cycleNodes) { if (recursionStack.count(module)) { cycleNodes.push_back(module); return true; } if (visited.count(module)) { return false; } visited.insert(module); recursionStack.insert(module); for (const string& neighbor : graph[module]) { if (detectCycle(neighbor, graph, visited, recursionStack, cycleNodes)) { if (find(cycleNodes.begin(), cycleNodes.end(), module) == cycleNodes.end()) { cycleNodes.push_back(module); } return true; } } recursionStack.erase(module); return false; } int main() { string modulesStr, depsStr; getline(cin, modulesStr); getline(cin, depsStr); vector<string> modules; istringstream iss(modulesStr); string module; while (getline(iss, module, ',')) { modules.push_back(module.substr(0, module.find_last_not_of(" \t") + 1)); } unordered_map<string, vector<string>> graph; for (const string& m : modules) { graph[m] = vector<string>(); } istringstream depsIss(depsStr); string dep; while (getline(depsIss, dep, ',')) { size_t pos = dep.find("<-"); string dependent = dep.substr(0, pos); string dependency = dep.substr(pos + 2); dependent = dependent.substr(dependent.find_first_not_of(" \t")); dependency = dependency.substr(dependency.find_first_not_of(" \t")); graph[dependency].push_back(dependent); } unordered_set<string> visited; unordered_set<string> recursionStack; vector<string> cycleNodes; for (const string& m : modules) { if (detectCycle(m, graph, visited, recursionStack, cycleNodes)) { break; } } cout << cycleNodes.size() << endl; return 0; }

C实现

#include <stdio.h> #include <stdlib.h> #include <string.h> #include <stdbool.h> #define MAX_MODULES 100 typedef struct { char name[10]; int edgeCount; char edges[MAX_MODULES][10]; } Module; Module graph[MAX_MODULES]; int moduleCount = 0; int findModuleIndex(const char* name) { for (int i = 0; i < moduleCount; i++) { if (strcmp(graph[i].name, name) == 0) { return i; } } return -1; } bool detectCycle(int moduleIdx, bool visited[], bool recursionStack[], int* cycleSize) { if (recursionStack[moduleIdx]) { (*cycleSize)++; return true; } if (visited[moduleIdx]) { return false; } visited[moduleIdx] = true; recursionStack[moduleIdx] = true; for (int i = 0; i < graph[moduleIdx].edgeCount; i++) { int neighborIdx = findModuleIndex(graph[moduleIdx].edges[i]); if (detectCycle(neighborIdx, visited, recursionStack, cycleSize)) { if (*cycleSize > 0) { (*cycleSize)++; return true; } } } recursionStack[moduleIdx] = false; return false; } int main() { char modulesStr[1000]; fgets(modulesStr, sizeof(modulesStr), stdin); modulesStr[strcspn(modulesStr, "\n")] = '\0'; char* token = strtok(modulesStr, ","); while (token != NULL) { strcpy(graph[moduleCount].name, token); graph[moduleCount].edgeCount = 0; moduleCount++; token = strtok(NULL, ","); } char depsStr[1000]; fgets(depsStr, sizeof(depsStr), stdin); depsStr[strcspn(depsStr, "\n")] = '\0'; token = strtok(depsStr, ","); while (token != NULL) { char* arrow = strstr(token, "<-"); if (arrow != NULL) { char dependent[10], dependency[10]; strncpy(dependent, token, arrow - token); dependent[arrow - token] = '\0'; strcpy(dependency, arrow + 2); int depIdx = findModuleIndex(dependency); strcpy(graph[depIdx].edges[graph[depIdx].edgeCount], dependent); graph[depIdx].edgeCount++; } token = strtok(NULL, ","); } bool visited[MAX_MODULES] = {false}; bool recursionStack[MAX_MODULES] = {false}; int cycleSize = 0; for (int i = 0; i < moduleCount; i++) { if (detectCycle(i, visited, recursionStack, &cycleSize)) { break; } } printf("%d\n", cycleSize > 0 ? cycleSize - 1 : 0); return 0; }

JavaScript实现

const readline = require('readline'); const rl = readline.createInterface({ input: process.stdin, output: process.stdout }); let modules = []; let dependencies = []; rl.on('line', (line) => { if (modules.length === 0) { modules = line.trim().split(',').map(m => m.trim()); } else { dependencies = line.trim().split(',').map(d => d.trim()); solve(); rl.close(); } }); function solve() { const graph = {}; modules.forEach(m => { graph[m] = []; }); dependencies.forEach(dep => { const [dependent, dependency] = dep.split('<-').map(s => s.trim()); graph[dependency].push(dependent); }); const visited = new Set(); const recursionStack = new Set(); let cycleNodes = []; function detectCycle(module) { if (recursionStack.has(module)) { cycleNodes.push(module); return true; } if (visited.has(module)) { return false; } visited.add(module); recursionStack.add(module); for (const neighbor of graph[module]) { if (detectCycle(neighbor)) { if (!cycleNodes.includes(module)) { cycleNodes.push(module); } return true; } } recursionStack.delete(module); return false; } for (const module of modules) { if (detectCycle(module)) { break; } } console.log(cycleNodes.length); }