华为OD机试真题:主次关联成环警告
2026华为OD机试双机位C卷 – 华为OD上机考试双机位C卷 200分题型
其它语言题解点击跳转：华为OD机试双机位C卷:主次关联成环警告（C/C++/Java/Python/Go/JS）
题目描述
在ICT运维领域，现网运维工程师面向对设备上报的众多告警，往往需要筛选出最主要的告警优先处理，次等级的告警或许为同一个根因导致的告警，处理优先级会放后或者不处理，这样就诞生出主次关联告警的概念。给定一系列告警的主次关联关系，判断是否存在如下情况：
- 情况1：同1个告警是否存在多个主告警。
- 情况2：输入的主次关联关系中是否存在环路。
输入描述
每个主次关联关系单独一行输入，输入形式为"主告警 次告警"。
例如
25aba 68vup
25aba为主告警，68vup为次告警，以空格分割，主次告警的格式都为小写字母+数字组成，1<=告警名称长度 <= 256。
输出描述
输出要求为指定格式字符串：
用例1
输入
a b
c b
输出
[1001,(b)]
用例2
输入
a b
b a
输出
[1002,cycle]
说明
主次关联关系为a->b->a,关系成环。
题解
思路：拓扑排序
c++
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
unordered_map<string, int> id; // 告警名 -> id
vector<string> name; // id -> 告警名
vector<vector<int>> graph; // 邻接表
vector<int> 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：同一个告警有多个主告警
vector<string> 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)
queue<int> q;
vector<int> 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;
}
