主次关联成环警告华为OD机试双机位C卷 - 华为OD上机考试双机位C卷 100分题型华为OD机试双机位C卷真题目录点击查看: 华为OD机试双机位C卷真题题库目录机考题库 算法考点详解题目描述在ICT运维领域现网运维工程师面向对设备上报的众多告警往往需要筛选出最主要的告警优先处理次等级的告警或许为同一个根因导致的告警处理优先级会放后或者不处理这样就诞生出主次关联告警的概念。给定一系列告警的主次关联关系判断是否存在如下情况情况1同1个告警是否存在多个主告警。情况2输入的主次关联关系中是否存在环路。输入描述每个主次关联关系单独一行输入输入形式为主告警 次告警。例如25aba 68vup25aba为主告警68vup为次告警以空格分割主次告警的格式都为小写字母数字组成1告警名称长度 256。输出描述输出要求为指定格式字符串如果给定的主次关联关系中同一个告警关联多个主告警输出格式为[1001,(b,d,e)]表示告警b有多个主告警按字母序排序。如果给定的主次关联关系中存在环路输出格式为[1002,cycle]如果上述两种异常情况均不存在输出[1003,Verified]如果主次告警关系中同时存在1-2中多种情况输出检查码最小的结果用例1输入a b c b输出[1001,(b)]用例2输入a b b a输出[1002,cycle]说明主次关联关系为a-b-a,关系成环。题解思路拓扑排序这个题目可抽象为有向图具体告警理解为节点。[主告警 次告警]看作一条主告警 - 次告警的边。接下来就是考虑上述两种情况怎么在有向图中求解情况1同1个告警是否存在多个主告警, 这个可以通过拓扑排序的入度来解决如果一个节点的入度大于1说明存在情况1。记录下所有入度 1告警然后升序排序按照题目要求输出即可。情况2输入的主次关联关系中是否存在环路。 这是利用拓扑排序的特性来处理如果是有向无环图拓扑排序是可以全部处理全部节点。如果处理节点数量 实际节点数则说明存在环(存在环的部分有节点入度拓扑排序过程中不会变为0)按照1 2 的分析实现代码即可具体代码逻辑参照下面代码。c#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); unordered_mapstring, int id; // 告警名 - id vectorstring name; // id - 告警名 vectorvectorint graph; // 邻接表 vectorint indegree; // 入度 string parent, child; // 读取直到 EOF while (cin parent child) { // 分配id if (!id.count(parent)) { int newId id.size(); id[parent] newId; name.push_back(parent); graph.push_back({}); indegree.push_back(0); } if (!id.count(child)) { int newId id.size(); id[child] newId; name.push_back(child); graph.push_back({}); indegree.push_back(0); } int u id[parent]; int v id[child]; graph[u].push_back(v); indegree[v]; } int n id.size(); // 情况1同一个告警有多个主告警 vectorstring multiParent; for (int i 0; i n; i) { // 入度大于1说明关联多个 if (indegree[i] 1) { multiParent.push_back(name[i]); } } // 直接输出 if (!multiParent.empty()) { sort(multiParent.begin(), multiParent.end()); cout [1001,(; for (size_t i 0; i multiParent.size(); i) { cout multiParent[i]; if (i ! multiParent.size() - 1) cout ,; } cout )]; return 0; } // 情况2检测环拓扑排序 处理总结点 实际节点数说明存在环(成环节点的数量入度不会变为0) queueint q; vectorint indeg indegree; for (int i 0; i n; i) { if (indeg[i] 0) { q.push(i); } } int count 0; while (!q.empty()) { int u q.front(); q.pop(); count; for (int v : graph[u]) { indeg[v]--; if (indeg[v] 0) { q.push(v); } } } if (count n) { cout [1002,cycle]; return 0; } // 正常 cout [1003,Verified]; return 0; }JAVAimport java.util.*; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); // 告警名 - id MapString, Integer id new HashMap(); // id - 告警名 ListString name new ArrayList(); // 邻接表 ListListInteger graph new ArrayList(); // 入度 ListInteger indegree new ArrayList(); // 读取直到 EOF while (sc.hasNext()) { String parent sc.next(); String child sc.next(); if (!id.containsKey(parent)) { int newId id.size(); id.put(parent, newId); name.add(parent); graph.add(new ArrayList()); indegree.add(0); } if (!id.containsKey(child)) { int newId id.size(); id.put(child, newId); name.add(child); graph.add(new ArrayList()); indegree.add(0); } int u id.get(parent); int v id.get(child); graph.get(u).add(v); indegree.set(v, indegree.get(v) 1); } int n id.size(); // 情况1同一个告警有多个主告警 ListString multiParent new ArrayList(); for (int i 0; i n; i) { if (indegree.get(i) 1) { multiParent.add(name.get(i)); } } if (!multiParent.isEmpty()) { Collections.sort(multiParent); System.out.print([1001,(); for (int i 0; i multiParent.size(); i) { System.out.print(multiParent.get(i)); if (i ! multiParent.size() - 1) System.out.print(,); } System.out.print()]); return; } // 情况2检测环拓扑排序 QueueInteger q new LinkedList(); int[] indeg new int[n]; for (int i 0; i n; i) { indeg[i] indegree.get(i); if (indeg[i] 0) q.offer(i); } int count 0; while (!q.isEmpty()) { int u q.poll(); count; for (int v : graph.get(u)) { indeg[v]--; if (indeg[v] 0) q.offer(v); } } if (count n) { System.out.println([1002,cycle]); return; } // 正常 System.out.println([1003,Verified]); } }Pythonimportsysfromcollectionsimportdeque id_map{}name[]# 边的关系graph[]# 节点入度indegree[]# 读取直到 EOFforlineinsys.stdin:parent,childline.split()//分配idifparentnotinid_map:new_idlen(id_map)id_map[parent]new_id name.append(parent)graph.append([])indegree.append(0)ifchildnotinid_map:new_idlen(id_map)id_map[child]new_id name.append(child)graph.append([])indegree.append(0)uid_map[parent]vid_map[child]graph[u].append(v)indegree[v]1nlen(id_map)# 情况1同一个告警有多个主告警multi_parent[]foriinrange(n):ifindegree[i]1:multi_parent.append(name[i])ifmulti_parent:multi_parent.sort()print([1001,(,.join(multi_parent))])sys.exit()# 情况2检测环拓扑排序qdeque()indegindegree[:]foriinrange(n):ifindeg[i]0:q.append(i)count0whileq:uq.popleft()count1forvingraph[u]:indeg[v]-1ifindeg[v]0:q.append(v)ifcountn:print([1002,cycle])else:print([1003,Verified])JavaScriptconstreadlinerequire(readline);// 创建 readline 接口constrlreadline.createInterface({input:process.stdin,output:process.stdout});// 告警名 - idconstidnewMap();// id - 告警名constname[];// 邻接表constgraph[];// 入度constindegree[];rl.on(line,(line){if(!line.trim())return;const[parent,child]line.trim().split(/\s/);// 分配 idif(!id.has(parent)){constnewIdid.size;id.set(parent,newId);name.push(parent);graph.push([]);indegree.push(0);}if(!id.has(child)){constnewIdid.size;id.set(child,newId);name.push(child);graph.push([]);indegree.push(0);}constuid.get(parent);constvid.get(child);graph[u].push(v);indegree[v];});// 输入结束rl.on(close,(){constnid.size;// 情况1同一个告警有多个主告警letmultiParent[];for(leti0;in;i){// 入度大于1说明关联多个if(indegree[i]1){multiParent.push(name[i]);}}// 直接输出if(multiParent.length0){multiParent.sort();process.stdout.write([1001,();for(leti0;imultiParent.length;i){process.stdout.write(multiParent[i]);if(i!multiParent.length-1)process.stdout.write(,);}process.stdout.write()]);return;}// 情况2检测环拓扑排序// 处理总结点 实际节点数说明存在环constindeg[...indegree];constqueue[];for(leti0;in;i){if(indeg[i]0){queue.push(i);}}letcount0;while(queue.length){constuqueue.shift();count;for(constvofgraph[u]){indeg[v]--;if(indeg[v]0){queue.push(v);}}}if(countn){console.log([1002,cycle]);return;}// 正常console.log([1003,Verified]);});Gopackagemainimport(bufiofmtossort)funcmain(){id:map[string]int{}name:[]string{}graph:[][]int{}indegree:[]int{}scanner:bufio.NewScanner(os.Stdin)// 读取直到 EOFforscanner.Scan(){varparent,childstringfmt.Sscanf(scanner.Text(),%s %s,parent,child)if_,ok:id[parent];!ok{newId:len(id)id[parent]newId nameappend(name,parent)graphappend(graph,[]int{})indegreeappend(indegree,0)}if_,ok:id[child];!ok{newId:len(id)id[child]newId nameappend(name,child)graphappend(graph,[]int{})indegreeappend(indegree,0)}u:id[parent]v:id[child]graph[u]append(graph[u],v)indegree[v]}n:len(id)// 情况1多个主告警multiParent:[]string{}fori:0;in;i{// 入度大于1ifindegree[i]1{multiParentappend(multiParent,name[i])}}iflen(multiParent)0{sort.Strings(multiParent)fmt.Print([1001,()fori:0;ilen(multiParent);i{fmt.Print(multiParent[i])ifi!len(multiParent)-1{fmt.Print(,)}}fmt.Print()])return}// 拓扑排序检测环queue:[]int{}indeg:make([]int,n)copy(indeg,indegree)fori:0;in;i{ifindeg[i]0{queueappend(queue,i)}}count:0forlen(queue)0{u:queue[0]queuequeue[1:]countfor_,v:rangegraph[u]{indeg[v]--ifindeg[v]0{queueappend(queue,v)}}}ifcountn{fmt.Println([1002,cycle])}else{fmt.Println([1003,Verified])}}C语言#includestdio.h#includestring.h#includestdlib.h#defineMAXN10000#defineMAXL260// id - 告警名charnames[MAXN][MAXL];// 邻接表intgraph[MAXN][MAXN];intgraphSize[MAXN];// 入度intindegree[MAXN];// 获取字符串对应 id不存在就创建intgetId(char*s,int*n){for(inti0;i*n;i){if(strcmp(names[i],s)0)returni;}strcpy(names[*n],s);return(*n);}// 字符串排序比较函数intcmp(constvoid*a,constvoid*b){returnstrcmp(*(char**)a,*(char**)b);}intmain(){charparent[MAXL],child[MAXL];intn0;// 读取直到 EOFwhile(scanf(%s %s,parent,child)!EOF){intugetId(parent,n);intvgetId(child,n);graph[u][graphSize[u]]v;indegree[v];}// 情况1同一个告警有多个主告警char*multi[MAXN];intm0;for(inti0;in;i){if(indegree[i]1){multi[m]names[i];}}if(m0){qsort(multi,m,sizeof(char*),cmp);printf([1001,();for(inti0;im;i){printf(%s,multi[i]);if(i!m-1)printf(,);}printf()]);return0;}// 情况2拓扑排序检测环intqueue[MAXN];intfront0,rear0;intindeg[MAXN];memcpy(indeg,indegree,sizeof(int)*n);// 入度为0入队for(inti0;in;i){if(indeg[i]0){queue[rear]i;}}intcount0;while(frontrear){intuqueue[front];count;for(inti0;igraphSize[u];i){intvgraph[u][i];indeg[v]--;if(indeg[v]0){queue[rear]v;}}}if(countn)printf([1002,cycle]);elseprintf([1003,Verified]);return0;}- 华为OD机试真题 主次关联成环警告 - 华为OD机考真题 主次关联成环警告 - 华为OD机试双机位C卷 - 华为OD机考双机位C卷 - 华为OD上机考试双机位C卷 - 华为 OD 双机位C卷 - 华为 OD 上机考试 双机位C卷 2025 -华为OD机考双机位C卷真题题库 - 主次关联成环警告