一、题目

在ICT运维领域，现网运维工程师面向对设备上报的众多告警，往往需要筛选出最主要的告警优先处理，次等级的告警或许为同一个根因导致的告警，处理优先级会放后或者不处理，这样就诞生出主次关联告警的概念。给定一系列告警的主次关联关系，判断是否存在如下情况：

情况1：同1个告警是否存在多个主告警。
情况2：输入的主次关联关系中是否存在环路。
输入描述
每个主次关联关系单独一行输入，输入形式为"主告警 次告警"。

例如

25aba 68vup
1
25aba为主告警，68vup为次告警，以空格分割，主次告警的格式都为小写字母+数字组成，1<=告警名称长度 <= 256。

输出描述
输出要求为指定格式字符串：

1、如果给定的主次关联关系中，同一个告警关联多个主告警，输出格式为[1001,(b,d,e)]表示告警b有多个主告警，按字母序排序。

2、如果给定的主次关联关系中存在环路，输出格式为[1002,cycle]。

3、 如果上述两种异常情况均不存在，输出[1003,Verified]。

4、如果主次告警关系中，同时存在1-2中多种情况，输出检查码最小的结果。


示例1

输入：

a b
c b

输出：

[1001,(b)]
 

示例2

输入：

a b
b a

输出：

[1002,cycle]

这是一道典型的图论（Graph Theory）应用题，主要考察有向图的入度统计和环路检测。

二、解题思路

我们将告警名称看作图的节点（Node），主次关系 主 -> 次 看作有向边（Edge）。

  • 主告警 →→ 次告警：即 A→B ，表示 A 是 B 的主告警。

1. 核心检测逻辑

情况 1：同一个告警存在多个主告警

  • 图论含义：某个节点的入度（In-degree）大于 1。
  • 检测方法：
    • 使用哈希表（Map）记录每个“次告警”对应的所有“主告警”列表。
    • 遍历输入，若发现某个次告警已经存在于 Map 中且对应的主告警列表不为空，且新加入的主告警与已有的不同，则标记该次告警为“多主”。
    • 注意：题目要求输出格式为 [1001,(b,d,e)]，其中括号内是按字母序排序的主告警列表？
      • 仔细审题：示例输出 [1001,(b)]。输入是 a b 和 c b。这里 b 是次告警，a 和 c 是主告警。
      • 示例输出显示的是 (b)，这看起来像是列出了有多个主告警的那个“次告警”，而不是列出它的所有主告警。
      • 让我们再读一遍题目描述：“输出格式为 [1001,(b,d,e)] 表示告警 b 有多个主告警”。
      • 修正理解：括号里的 b, d, e 指的是那些拥有多个主告警的“次告警”本身，按字母序排序。而不是列出它们的主告警。
      • 验证示例 1：
        • 输入：a b, c b
        • b 的主告警有 a 和 c（2个）。
        • 输出：[1001,(b)]。
        • 结论：括号内是冲突的次告警名称列表。

情况 2：存在环路

  • 图论含义：有向图中存在环（Cycle）。
  • 检测方法：
    • 使用 DFS（深度优先搜索） + 三色标记法，或者 拓扑排序（Kahn 算法）。
    • DFS 三色法：
      • 0: 未访问
      • 1: 正在访问中（当前递归栈中）
      • 2: 已访问完成
      • 若在 DFS 过程中遇到状态为 1 的节点，说明存在环路。
    • 拓扑排序法：
      • 统计所有节点入度。
      • 将入度为 0 的节点入队。
      • 每次出队一个节点，将其邻居入度减 1，若减为 0 则入队。
      • 若最终处理的节点数 < 总节点数，说明存在环。
    • 选择：DFS 实现起来代码量较少，且容易直接判断是否存在环。

2. 优先级处理

题目要求：

  1. 若同时存在多种情况，输出检查码最小的结果。
  2. 检查码定义：情况 1 是 1001，情况 2 是 1002。
  3. 策略：
    • 先检查情况 1（多主告警）。如果发现，直接记录并准备输出（因为 1001 < 1002）。
    • 如果情况 1 不存在，再检查情况 2（环路）。
    • 如果都不存在，输出 1003。
    • 特例：如果题目意思是“只要有多主就报 1001，不管有没有环”，那逻辑很简单。如果题目隐含“即使有环，只要有多主也优先报 1001”，那么顺序就是：先查多主 -> 有则返回；无则查环 -> 有则返回；无则返回 1003。

3. 数据结构设计

  • Map<String, List<String>> incomingEdges: 记录每个次告警对应的主告警列表，用于检测情况 1。
  • Map<String, List<String>> adjList: 邻接表，记录 主 -> [次]，用于构建图进行环路检测。
  • Set<String> allNodes: 记录所有出现过的告警名称。

三、Code实现

1、Java ✅️

import java.util.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class AlarmRelationChecker {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line;
        
        // 数据结构
        // 记录每个次告警对应的主告警列表 (用于检测情况1)
        Map<String, List<String>> incomingMap = new HashMap<>();
        // 邻接表 (用于检测情况2: 主 -> 次)
        Map<String, List<String>> adjList = new HashMap<>();
        // 所有节点集合
        Set<String> allNodes = new HashSet<>();

        while ((line = br.readLine()) != null && !line.trim().isEmpty()) {
            String[] parts = line.trim().split("\\s+");
            if (parts.length != 2) continue;
            
            String main = parts[0];
            String sub = parts[1];

            allNodes.add(main);
            allNodes.add(sub);

            // 构建入度映射
            incomingMap.computeIfAbsent(sub, k -> new ArrayList<>()).add(main);
            
            // 构建邻接表
            adjList.computeIfAbsent(main, k -> new ArrayList<>()).add(sub);
            // 确保次节点也在邻接表中（即使没有出边）
            adjList.putIfAbsent(sub, new ArrayList<>());
        }

        // 1. 检查情况 1：同1个告警是否存在多个主告警
        List<String> multiMainSubs = new ArrayList<>();
        for (Map.Entry<String, List<String>> entry : incomingMap.entrySet()) {
            String subAlarm = entry.getKey();
            List<String> mains = entry.getValue();
            // 去重后看数量是否大于1 (防止重复输入相同的边 a b, a b)
            Set<String> uniqueMains = new HashSet<>(mains);
            if (uniqueMains.size() > 1) {
                multiMainSubs.add(subAlarm);
            }
        }

        if (!multiMainSubs.isEmpty()) {
            Collections.sort(multiMainSubs);
            System.out.println(formatOutput(1001, multiMainSubs));
            return; // 优先级最高，直接返回
        }

        // 2. 检查情况 2：是否存在环路 (DFS)
        if (hasCycle(adjList, allNodes)) {
            System.out.println("[1002,cycle]");
            return;
        }

        // 3. 正常情况
        System.out.println("[1003,Verified]");
    }

    /**
     * 使用 DFS 三色法检测环路
     * 0: 未访问, 1: 访问中, 2: 已完成
     */
    private static boolean hasCycle(Map<String, List<String>> adjList, Set<String> nodes) {
        Map<String, Integer> state = new HashMap<>();
        for (String node : nodes) {
            state.put(node, 0);
        }

        for (String node : nodes) {
            if (state.get(node) == 0) {
                if (dfsDetectCycle(node, adjList, state)) {
                    return true;
                }
            }
        }
        return false;
    }

    private static boolean dfsDetectCycle(String u, Map<String, List<String>> adjList, Map<String, Integer> state) {
        state.put(u, 1); // 标记为正在访问

        for (String v : adjList.getOrDefault(u, new ArrayList<>())) {
            int vState = state.getOrDefault(v, 0);
            if (vState == 1) {
                // 遇到正在访问的节点，说明有环
                return true;
            } else if (vState == 0) {
                if (dfsDetectCycle(v, adjList, state)) {
                    return true;
                }
            }
        }

        state.put(u, 2); // 标记为已完成
        return false;
    }

    private static String formatOutput(int code, List<String> list) {
        StringBuilder sb = new StringBuilder();
        sb.append("[").append(code).",(");
        for (int i = 0; i < list.size(); i++) {
            sb.append(list.get(i));
            if (i < list.size() - 1) {
                sb.append(",");
            }
        }
        sb.append(")]");
        return sb.toString();
    }
}

2、Go ✅

package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
	"strings"
)

func main() {
	scanner := bufio.NewScanner(os.Stdin)

	// 数据结构
	// incomingMap: subAlarm -> [mainAlarms]
	incomingMap := make(map[string][]string)
	// adjList: mainAlarm -> [subAlarms]
	adjList := make(map[string][]string)
	// allNodes
	allNodes := make(map[string]bool)

	for scanner.Scan() {
		line := strings.TrimSpace(scanner.Text())
		if line == "" {
			continue
		}
		parts := strings.Fields(line)
		if len(parts) != 2 {
			continue
		}
		main := parts[0]
		sub := parts[1]

		allNodes[main] = true
		allNodes[sub] = true

		incomingMap[sub] = append(incomingMap[sub], main)
		adjList[main] = append(adjList[main], sub)
		// 确保 sub 也在邻接表中
		if _, exists := adjList[sub]; !exists {
			adjList[sub] = []string{}
		}
	}

	// 1. 检查情况 1：多主告警
	var multiMainSubs []string
	for sub, mains := range incomingMap {
		uniqueMains := make(map[string]bool)
		for _, m := range mains {
			uniqueMains[m] = true
		}
		if len(uniqueMains) > 1 {
			multiMainSubs = append(multiMainSubs, sub)
		}
	}

	if len(multiMainSubs) > 0 {
		sort.Strings(multiMainSubs)
		fmt.Println(formatOutput(1001, multiMainSubs))
		return
	}

	// 2. 检查情况 2：环路
	if hasCycle(adjList, allNodes) {
		fmt.Println("[1002,cycle]")
		return
	}

	// 3. 正常
	fmt.Println("[1003,Verified]")
}

// DFS 三色法检测环
// 0: unvisited, 1: visiting, 2: visited
func hasCycle(adjList map[string][]string, nodes map[string]bool) bool {
	state := make(map[string]int)
	for node := range nodes {
		state[node] = 0
	}

	var dfs func(u string) bool
	dfs = func(u string) bool {
		state[u] = 1 // visiting

		for _, v := range adjList[u] {
			vState, exists := state[v]
			if !exists {
				// 理论上所有节点都在 nodes 里，这里做个防御
				continue
			}
			if vState == 1 {
				return true // 发现环
			}
			if vState == 0 {
				if dfs(v) {
					return true
				}
			}
		}
		state[u] = 2 // visited
		return false
	}

	for node := range nodes {
		if state[node] == 0 {
			if dfs(node) {
				return true
			}
		}
	}
	return false
}

func formatOutput(code int, list []string) string {
	var sb strings.Builder
	sb.WriteString(fmt.Sprintf("[%d,(", code))
	for i, item := range list {
		sb.WriteString(item)
		if i < len(list)-1 {
			sb.WriteString(",")
		}
	}
	sb.WriteString(")]")
	return sb.String()
}

 四、关键点总结

 关键逻辑点：

  • 多主判断：必须对每个次告警的主告警列表进行去重。如果输入是 a b 和 a b（重复行），这不算多主，只有 a b 和 c b 才算。
  • 优先级：代码逻辑严格遵循 if (多主) return; else if (环) return; else verified，满足题目“输出检查码最小”的要求（1001 < 1002）。
  • 环路检测：使用 DFS 三色法是检测有向图环的标准高效方法，时间复杂度 O(V+E) 。
# 算法 # 深度优先 # java # golang
Logo
https://edu.csdn.net/learn/39067/627173?utm_source=2019755004

汇聚全球AI编程工具，助力开发者即刻编程。

更多推荐

cover

一个 API 入口调用多个大模型：AiiOnly客户端 + CC Switch 打通 Codex AI编程流程

avatar AI编程社区
cover

VSCode Claude Code + MiMo 中转免登录完整配置教程（解决原生登录弹窗 + 模型报错）

avatar AI编程社区
cover

从零开始做一个属于自己的 Skill（保姆级教程）

avatar AI编程社区