刷题笔记合集🔗

主次关联告警成环检测

问题描述

在 ICT 运维领域，小兰作为现网运维工程师，面对设备上报的众多告警时，往往需要筛选出最主要的告警优先处理。次等级的告警或者为同一个根因导致的告警，处理优先级会放后或者不处理，这样就诞生了主次关联告警的概念。

小毛给 小兰 提供了一系列告警的主次关联关系，小兰 需要判断是否存在如下情况：

• 情况1：同一个次告警是否关联了多个主告警
• 情况2：输入的主次关联关系中是否存在环路

输入格式

每个主次关联关系单独一行输入，格式为主告警和次告警，用空格分隔。

告警名称由小写字母和数字组成，长度在 到 之间。

输出格式

输出格式为：

1. 若存在情况1，输出校验码 1001，并列出所有关联了多个主告警的次告警名称（按升序）
2. 若存在情况2，输出校验码 1002，并加上 "cycle"
3. 若上述两种情况都不存在，输出校验码 1003，并加上 "Verified"
4. 若同时存在多种情况，则输出校验码最大的结果

样例输入

a b
c b

a b
b a

样例输出

[1001,(b)]

[1002,cycle]

数据范围

• 告警名称长度
• 关联关系数量
• 告警名称由小写字母和数字组成

题解

这道题目考查图论中的环检测和关系统计。让我们从问题本质来分析：

首先明确两个检测目标：一是找出被多个主告警关联的次告警，二是检测图中是否存在环路。

对于情况1的检测，可以用哈希表记录每个次告警对应的主告警集合。遍历所有输入关系时，将主告警加入到对应次告警的集合中。最后检查哪些次告警的主告警集合大小超过1。

对于情况2的环检测，这是一个经典的有向图环检测问题。可以使用拓扑排序的思想：如果图中存在环，那么拓扑排序无法处理所有节点。具体方法是维护每个节点的入度，不断移除入度为0的节点，如果最终处理的节点数小于总节点数，说明存在环。

算法步骤：

1. 用邻接表存储图结构，用集合记录每个次告警的主告警
2. 遍历输入，建立图关系并统计主次关联
3. 检查情况1：找出主告警数量大于1的次告警，按字典序排序
4. 检查情况2：使用拓扑排序检测环路
5. 根据检测结果和优先级规则输出相应格式

时间复杂度是 ，其中 是告警节点数， 是关联关系数。这个复杂度对于题目的数据范围是完全可以接受的。

参考代码

• Python

import sys
input = lambda: sys.stdin.readline().strip()

from collections import defaultdict, deque

# 存储图关系和父子关系
graph = defaultdict(list)  # 主->次的邻接表
parents = defaultdict(set)  # 次->主集合
nodes = set()  # 所有节点

# 读取输入直到EOF
while True:
    try:
        line = input()
        if not line:
            break
        main_alarm, sub_alarm = line.split()
        graph[main_alarm].append(sub_alarm)  # 建立主->次关系
        parents[sub_alarm].add(main_alarm)   # 记录次告警的主告警
        nodes.add(main_alarm)
        nodes.add(sub_alarm)
    except:
        break

# 检测情况1：多个主告警关联同一个次告警
multi_parent = []
for sub, main_set in parents.items():
    if len(main_set) > 1:  # 如果次告警有多个主告警
        multi_parent.append(sub)
multi_parent.sort()  # 按字典序排序

# 检测情况2：使用拓扑排序检测环路
in_deg = {node: 0 for node in nodes}  # 初始化入度
for main in graph:
    for sub in graph[main]:
        in_deg[sub] += 1  # 计算每个节点的入度

# 拓扑排序过程
queue = deque()
for node in nodes:
    if in_deg[node] == 0:  # 入度为0的节点加入队列
        queue.append(node)

processed = 0  # 处理的节点数
while queue:
    curr = queue.popleft()
    processed += 1
    for neighbor in graph[curr]:  # 处理当前节点的邻居
        in_deg[neighbor] -= 1
        if in_deg[neighbor] == 0:
            queue.append(neighbor)

# 判断结果
has_case1 = len(multi_parent) > 0
has_case2 = processed < len(nodes)  # 如果处理节点数小于总数，存在环

# 根据题目要求输出结果
if has_case1 and (not has_case2 or 1001 > 1002):
    print(f"[1001,({' '.join(multi_parent)})]")
elif has_case2:
    print("[1002,cycle]")
else:
    print("[1003,Verified]")

• Cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    // 数据结构定义
    map<string, vector<string>> adj;  // 邻接表
    map<string, set<string>> child_to_parent;  // 子节点到父节点集合
    set<string> all_nodes;  // 所有节点
    
    string from, to;
    // 读取所有边关系
    while (cin >> from >> to) {
        adj[from].push_back(to);  // 建立有向边
        child_to_parent[to].insert(from);  // 记录父子关系
        all_nodes.insert(from);
        all_nodes.insert(to);
    }
    
    // 找出有多个父节点的子节点
    vector<string> multi_parents;
    for (const auto& entry : child_to_parent) {
        if (en