解题思路

思路

• 每条规则 A -> B 是有向边。
• 先在规则图上用 DFS 三色标记 判环：0=未访，1=在栈，2=已完成；遇到回到“在栈”即有环。
• 若无环：对每个发生的告警做一次 DFS，找出它能到达的所有告警，这些都被它抑制。把所有发生告警的可达点并起来，最后输出 发生集合 - 被抑制集合，并按字典序升序。

复杂度分析

题目内容

在云音乐平台的分布式系统监控中，当出现服务故障时会产生多种类型的告警。为避免告警风暴，运维团队配置了告警抑制规则。一条抑制规则形如 $A->B$ ，表示当告警 $A$ 发生时，应该抑制(即不通知)告警 $B$ 。这种抑制关系具有传递性，即如果存在 $A->B$ 和 $B->C$ ，那么 $A$ 发生时也会抑制 $C$ 。然而，如果抑制规则配置存在循环抑制(例如 $A->B,B->C,C->A$)，将导致逻辑冲突，使得告警系统无法正确处理。

请实现一个功能，用于：

1.检查给定的抑制规则集合中是否存在循环抑制

2.处理告警事件，根据抑制规则输出最终需要通知的告警列表

输入描述

每组输入由如下部分构成，有多组输入，如遇到空行则输入结束

第一行：$M\, N,M、N$ 均为正整数，表示后续有 $M$ 条规则，$N$ 表示后续有 $N$ 条原始告警事件

$M$ 行规则，每一行为两个字符串 $A$ $B$，表示一条抑制规则 $A->B，A/B$ 均为不包含空格的字符串，字符串中间以空格分隔

$N$ 行告警名，每一个行是一个字符串，表示原始告警名

输出描述

如果存在循环抑制，输出字符串 $“CYCLE$ $DETECTED"$

如果没有循环，输出抑制处理后最终需要通知的告警(即未被任何其他发生的告警抑制的告警)，按告警名的字典序升序输出，每一行输出一个。

样例1

输入

2 3
A B
B C
C
B
D

输出

B
D

样例2

输入

3 2
A B
B C
C A
A
B

输出

CYCLE DETECTED