华为OD新系统机试真题 - 项目模块依赖构建顺序规划(C/C/Py/Java/Js/Go)华为OD机试真题 华为OD上机考试真题 4月26号 200分题型华为OD机试真题目录点击查看: 华为OD机试真题题库目录机考题库 算法考点详解题目描述某公司正在开发一个大型软件系统系统包含 N个模块每个模块之间存在构建依赖关系。例如模块 A 可能依赖于模块 B这意味着必须先构建模块 B才能构建模块 A。请根据依赖关系输出所有可能的模块构建顺序按照构建顺序排列模块名称要求每个合法的构建顺序作为一个结果多个结果按字典序排序后输出如果存在循环依赖依赖成环的情况则说明没有合法的构建顺序返回NULL输入描述第一行输入所有模块名称模块名只会由数字、大写字母、小写字母构成无分隔符。模块名称互不相同。模块数量 N≤100多个模块之间使用逗号分割。第二行输入依赖关系每个依赖关系为依赖模块,被依赖模块表示前者依赖后者。被依赖模块必须在依赖模块之前构建。多个依赖关系使用空格分割。依赖关系数量 100输出描述输出所有合法的构建顺序模块之间用空格分隔按字典序排序。保证合法构建顺序结果 10!存在循环依赖时输出NULL10!10×9×8×7×6×5×4×3×2×1用例1输入user,auth,database,api user,auth auth,database api,database输出database api auth user database auth api user database auth user api说明依赖关系user→auth→databaseapi→databasedatabase所有模块都依赖需要第一个构建合法拓扑排序有 3种按字典序排序后输出用例2输入A,B,C A,B B,C C,A输出NULL说明形成环 A→B→C→A存在循环依赖无法完成构建输出NULL。题解思路拓扑排序 递归回溯这道题本质是带限制的合法路径枚举 路径枚举采用递归回溯实现题目限制的每个模块之间存在构建依赖关系。例如模块 A 可能依赖于模块 B这意味着必须先构建模块 B才能构建模块 A。通过拓扑排序中的入度进行解决。本题的具体实现步骤为通过给出依赖构建有向图统计每个模块的入度(有多少前置模块数量)通过递归回溯枚举所有合法路径当枚举路径模块数量 总模块数量时结束按从前往后选择入度为0的路径加入当前枚举路径更新其后置模块的入度递归进行搜索回溯状态最后对当前结果按照字典序排序。c#includeiostream #includevector #includestring #include utility #include sstream #includealgorithm #includecmath #includeunordered_map #includeset using namespace std; // 通用 切割函数 函数 将字符串str根据delimiter进行切割 vectorstring split(const string str, const string delimiter) { vectorstring result; size_t start 0; size_t end str.find(delimiter); while (end ! string::npos) { result.push_back(str.substr(start, end - start)); start end delimiter.length(); end str.find(delimiter, start); } // 添加最后一个部分 result.push_back(str.substr(start)); return result; } void dfs(vectorstring name, unordered_mapstring, vectorstring graph, unordered_mapstring, int indegree, vectorstring path, vectorstring res) { if (path.size() name.size()) { string currentPath; for (int i 0; i name.size(); i) { currentPath path[i]; if (i ! name.size() - 1) { currentPath ; } } res.push_back(currentPath); return; } for (auto currentName : name) { if (indegree[currentName] ! 0) { continue; } indegree[currentName] -1; path.push_back(currentName); // 更新被依赖入度 for (auto nx : graph[currentName]) { indegree[nx]--; } dfs(name, graph, indegree, path, res); // 回溯 // 恢复入度 for (auto nx : graph[currentName]) { indegree[nx]; } path.pop_back(); indegree[currentName] 0; } } vectorstring getAllBuid(vectorstring name, vectorvectorstring dependencyGraph) { unordered_mapstring, vectorstring graph; // 统计入度 unordered_mapstring, int indegree; for (auto n : name) { indegree[n] 0; } // 用于边去重 setpairstring, string edges; // 处理边和入度 for (auto dependency : dependencyGraph) { string a dependency[0]; string b dependency[1]; if (!edges.count({b, a})) { edges.insert({b,a}); graph[b].push_back(a); indegree[a]; } } vectorstring res; vectorstring path; dfs(name, graph, indegree, path, res); // 结果排序 sort(res.begin(), res.end()); return res; } int main() { string input1; string input2; getline(cin, input1); getline(cin, input2); vectorstring name split(input1, ,); vectorstring dependency split(input2, ); vectorvectorstring dependencyGraph; for (int i 0; i dependency.size(); i) { dependencyGraph.push_back(split(dependency[i], ,)); } vectorstring res getAllBuid(name, dependencyGraph); if (res.empty()) { cout NULL; return 0; } // 输出结果 for (auto seq : res) { cout seq endl; } return 0; }JAVAimport java.util.*; public class Main { // DFS 搜索所有拓扑排序结果 static void dfs(ListString name, MapString, ListString graph, MapString, Integer indegree, ListString path, ListString res) { if (path.size() name.size()) { StringBuilder currentPath new StringBuilder(); for (int i 0; i name.size(); i) { currentPath.append(path.get(i)); if (i ! name.size() - 1) { currentPath.append( ); } } res.add(currentPath.toString()); return; } for (String currentName : name) { if (indegree.get(currentName) ! 0) continue; indegree.put(currentName, -1); path.add(currentName); // 更新被依赖入度 for (String nx : graph.getOrDefault(currentName, new ArrayList())) { indegree.put(nx, indegree.get(nx) - 1); } dfs(name, graph, indegree, path, res); // 回溯恢复入度 for (String nx : graph.getOrDefault(currentName, new ArrayList())) { indegree.put(nx, indegree.get(nx) 1); } path.remove(path.size() - 1); indegree.put(currentName, 0); } } static ListString getAllBuild(ListString name, ListListString dependencyGraph) { MapString, ListString graph new HashMap(); MapString, Integer indegree new HashMap(); // 初始化入度 for (String n : name) { indegree.put(n, 0); } // 边去重 SetString edges new HashSet(); for (ListString dep : dependencyGraph) { String a dep.get(0); String b dep.get(1); String key b - a; if (!edges.contains(key)) { edges.add(key); graph.computeIfAbsent(b, k - new ArrayList()).add(a); indegree.put(a, indegree.get(a) 1); } } ListString res new ArrayList(); dfs(name, graph, indegree, new ArrayList(), res); // 结果排序 Collections.sort(res); return res; } public static void main(String[] args) { Scanner sc new Scanner(System.in); String input1 sc.nextLine(); String input2 sc.nextLine(); ListString name Arrays.asList(input1.split(,)); String[] deps input2.split( ); ListListString dependencyGraph new ArrayList(); for (String d : deps) { dependencyGraph.add(Arrays.asList(d.split(,))); } ListString res getAllBuild(name, dependencyGraph); if (res.isEmpty()) { System.out.print(NULL); return; } for (String s : res) { System.out.println(s); } } }Pythonimportsys# DFS 搜索所有拓扑排序结果defdfs(name,graph,indegree,path,res):iflen(path)len(name):# 拼接路径res.append( .join(path))returnforcurrentinname:ifindegree[current]!0:continueindegree[current]-1path.append(current)# 更新被依赖入度fornxingraph.get(current,[]):indegree[nx]-1dfs(name,graph,indegree,path,res)# 回溯恢复入度fornxingraph.get(current,[]):indegree[nx]1path.pop()indegree[current]0defgetAllBuild(name,dependencyGraph):graph{}indegree{}# 初始化入度forninname:indegree[n]0edgesset()# 构建图 边去重fora,bindependencyGraph:if(b,a)notinedges:edges.add((b,a))graph.setdefault(b,[]).append(a)indegree[a]1res[]dfs(name,graph,indegree,[],res)res.sort()returnresif__name____main__:input1sys.stdin.readline().strip()input2sys.stdin.readline().strip()nameinput1.split(,)depsinput2.split()dependencyGraph[d.split(,)fordindeps]resgetAllBuild(name,dependencyGraph)ifnotres:print(NULL)else:forrinres:print(r)JavaScriptconstreadlinerequire(readline);constrlreadline.createInterface({input:process.stdin,output:process.stdout});letlines[];rl.on(line,(line){lines.push(line);});rl.on(close,(){// DFS 搜索所有拓扑排序结果functiondfs(name,graph,indegree,path,res){if(path.lengthname.length){res.push(path.join( ));return;}for(letcurrentofname){if(indegree[current]!0)continue;indegree[current]-1;path.push(current);// 更新被依赖入度for(letnxof(graph[current]||[])){indegree[nx]--;}dfs(name,graph,indegree,path,res);// 回溯恢复入度for(letnxof(graph[current]||[])){indegree[nx];}path.pop();indegree[current]0;}}functiongetAllBuild(name,dependencyGraph){letgraph{};letindegree{};// 初始化入度for(letnofname){indegree[n]0;}letedgesnewSet();for(let[a,b]ofdependencyGraph){letkeyb-a;if(!edges.has(key)){edges.add(key);if(!graph[b])graph[b][];graph[b].push(a);indegree[a];}}letres[];dfs(name,graph,indegree,[],res);res.sort();returnres;}letnamelines[0].split(,);letdepslines[1].split( );letdependencyGraphdeps.map(dd.split(,));letresgetAllBuild(name,dependencyGraph);if(res.length0){console.log(NULL);}else{res.forEach(rconsole.log(r));}});Gopackagemainimport(bufiofmtossortstrings)// DFS 搜索所有拓扑排序结果funcdfs(name[]string,graphmap[string][]string,indegreemap[string]int,path[]string,res*[]string){iflen(path)len(name){*resappend(*res,strings.Join(path, ))return}for_,current:rangename{ifindegree[current]!0{continue}indegree[current]-1pathappend(path,current)// 更新被依赖入度for_,nx:rangegraph[current]{indegree[nx]--}dfs(name,graph,indegree,path,res)// 回溯恢复入度for_,nx:rangegraph[current]{indegree[nx]}pathpath[:len(path)-1]indegree[current]0}}funcgetAllBuild(name[]string,dependencyGraph[][]string)[]string{graph:make(map[string][]string)indegree:make(map[string]int)// 初始化入度for_,n:rangename{indegree[n]0}edges:make(map[string]bool)for_,dep:rangedependencyGraph{a,b:dep[0],dep[1]key:b-aif!edges[key]{edges[key]truegraph[b]append(graph[b],a)indegree[a]}}res:[]string{}dfs(name,graph,indegree,[]string{},res)sort.Strings(res)returnres}funcmain(){scanner:bufio.NewScanner(os.Stdin)scanner.Scan()input1:scanner.Text()scanner.Scan()input2:scanner.Text()name:strings.Split(input1,,)deps:strings.Split(input2, )vardependencyGraph[][]stringfor_,d:rangedeps{dependencyGraphappend(dependencyGraph,strings.Split(d,,))}res:getAllBuild(name,dependencyGraph)iflen(res)0{fmt.Println(NULL)return}for_,r:rangeres{fmt.Println(r)}}C语言#includestdio.h#includestring.h#includestdlib.h#defineMAXN105charnames[MAXN][20];intn;// 图邻接矩阵intgraph[MAXN][MAXN];// 入度intindegree[MAXN];// 路径intpath[MAXN];intused[MAXN];// 结果存储charres[400000][200];intresSize0;// 字符串排序保证字典序intcmp(constvoid*a,constvoid*b){returnstrcmp((char*)a,(char*)b);}// DFS 搜索所有拓扑排序结果voiddfs(intdepth){if(depthn){// 拼接路径chartemp[200]{0};for(inti0;in;i){strcat(temp,names[path[i]]);if(i!n-1)strcat(temp, );}strcpy(res[resSize],temp);return;}for(inti0;in;i){if(indegree[i]!0||used[i])continue;used[i]1;path[depth]i;// 更新被依赖入度for(intj0;jn;j){if(graph[i][j])indegree[j]--;}dfs(depth1);// 回溯恢复for(intj0;jn;j){if(graph[i][j])indegree[j];}used[i]0;}}intmain(){charinput1[10000],input2[10000];fgets(input1,sizeof(input1),stdin);fgets(input2,sizeof(input2),stdin);// 解析模块名char*tokenstrtok(input1,,\n);while(token){strcpy(names[n],token);tokenstrtok(NULL,,\n);}// 解析依赖关系tokenstrtok(input2, \n);while(token){chara[20],b[20];sscanf(token,%[^,],%s,a,b);intai-1,bi-1;for(inti0;in;i){if(strcmp(names[i],a)0)aii;if(strcmp(names[i],b)0)bii;}if(bi!-1ai!-1){graph[bi][ai]1;indegree[ai];}tokenstrtok(NULL, \n);}qsort(names,n,sizeof(names[0]),cmp);dfs(0);if(resSize0){printf(NULL\n);return0;}for(inti0;iresSize;i){printf(%s\n,res[i]);}return0;}