解题思路
思路
- 每条规则
A -> B 是有向边。
- 先在规则图上用 DFS 三色标记 判环：0=未访，1=在栈，2=已完成；遇到回到“在栈”即有环。
- 若无环：对每个发生的告警做一次 DFS，找出它能到达的所有告警，这些都被它抑制。把所有发生告警的可达点并起来，最后输出
发生集合 - 被抑制集合，并按字典序升序。
复杂度分析
- 设结点数
V、边数 E、去重后发生告警数 K。
- 判环：
O(V+E)；抑制：对每个告警做 DFS，总体 O(V+E) 级别；输出排序 O(K log K)。
- 空间：
O(V+E)。
代码实现
import sys
sys.setrecursionlimit(1 << 25)
def detect_cycle(adj):
color = {} # 0 未访, 1 在栈, 2 完成
def dfs(u):
c = color.get(u, 0)
if c == 1: return True
if c == 2: return False
color[u] = 1
for v in adj.get(u, []):
if dfs(v): return True
color[u] = 2
return False
for u in adj:
if color.get(u, 0) == 0 and dfs(u):
return True
return False
def solve_one(M, N, rules, alerts):
adj = {}
for a, b in rules:
adj.setdefault(a, []).append(b)
adj.setdefault(b, adj.get(b, []))
for s in alerts:
adj.setdefault(s, adj.get(s, []))
if detect_cycle(adj):
print("CYCLE DETECTED")
return
alerts_set = set(alerts)
suppressed = set()
# 对每个发生的告警做 DFS，收集可达点
for s in alerts_set:
stack = [s]
seen = set()
while stack:
u = stack.pop()
for v in adj.get(u, []):
if v not in seen:
seen.add(v)
stack.append(v)
suppressed |= seen
ans = sorted(alerts_set - suppressed)
for x in ans:
print(x)
def main():
lines = [ln.rstrip("\n") for ln in sys.stdin.read().splitlines()]
i = 0
while i < len(lines):
line = lines[i].strip()
if not line: break
M, N = map(int, line.split())
i += 1
rules = []
for _ in range(M):
a, b = lines[i].split()
rules.append((a, b))
i += 1
alerts = []
for _ in range(N):
alerts.append(lines[i].strip())
i += 1
solve_one(M, N, rules, alerts)
if __name__ == "__main__":
main()
#include <bits/stdc++.h>
using namespace std;
unordered_map<string, vector<string>> adj;
bool dfsCycle(const string& u, unordered_map<string,int>& color) {
int c = color.count(u) ? color[u] : 0;
if (c == 1) return true;
if (c == 2) return false;
color[u] = 1;
for (auto &v : adj[u]) {
if (dfsCycle(v, color)) return true;
}
color[u] = 2;
return false;
}
bool detectCycle() {
unordered_map<string,int> color;
for (auto &kv : adj) {
if (!color.count(kv.first) && dfsCycle(kv.first, color)) return true;
}
return false;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string line;
while (true) {
if (!getline(cin, line)) break;
if (line.size() == 0) break;
stringstream ss(line);
int M, N; ss >> M >> N;
adj.clear();
vector<pair<string,string>> rules(M);
for (int i = 0; i < M; ++i) {
getline(cin, line);
string a, b; stringstream sr(line); sr >> a >> b;
rules[i] = {a, b};
adj[a]; adj[b]; // 建键
}
vector<string> alerts(N);
for (int i = 0; i < N; ++i) {
getline(cin, alerts[i]);
adj[alerts[i]]; // 建键
}
for (auto &p : rules) adj[p.first].push_back(p.second);
if (detectCycle()) {
cout << "CYCLE DETECTED\n";
continue;
}
unordered_set<string> occur(alerts.begin(), alerts.end());
unordered_set<string> suppressed;
for (auto &s : occur) {
vector<string> st = {s};
unordered_set<string> seen;
while (!st.empty()) {
string u = st.back(); st.pop_back();
for (auto &v : adj[u]) if (!seen.count(v)) {
seen.insert(v);
st.push_back(v);
}
}
suppressed.insert(seen.begin(), seen.end());
}
vector<string> ans;
for (auto &s : occur) if (!suppressed.count(s)) ans.push_back(s);
sort(ans.begin(), ans.end());
for (auto &x : ans) cout << x << "\n";
}
return 0;
}
import java.util.*;
import java.io.*;
public class Main {
static Map<String, List<String>> adj;
static boolean detectCycle() {
Map<String, Integer> color = new HashMap<>(); // 0 未, 1 栈, 2 完
for (String u : adj.keySet()) {
if (!color.containsKey(u) && dfs(u, color)) return true;
}
return false;
}
static boolean dfs(String u, Map<String, Integer> color) {
Integer c = color.getOrDefault(u, 0);
if (c == 1) return true;
if (c == 2) return false;
color.put(u, 1);
for (String v : adj.getOrDefault(u, Collections.emptyList())) {
if (dfs(v, color)) return true;
}
color.put(u, 2);
return false;
}
static void solveOne(int M, int N, List<String[]> rules, List<String> alerts) {
adj = new HashMap<>();
for (String[] r : rules) {
adj.computeIfAbsent(r[0], k -> new ArrayList<>()).add(r[1]);
adj.computeIfAbsent(r[1], k -> new ArrayList<>());
}
for (String s : alerts) adj.computeIfAbsent(s, k -> new ArrayList<>());
if (detectCycle()) {
System.out.println("CYCLE DETECTED");
return;
}
Set<String> occur = new HashSet<>(alerts);
Set<String> suppressed = new HashSet<>();
for (String s : occur) {
Deque<String> st = new ArrayDeque<>();
Set<String> seen = new HashSet<>();
st.push(s);
while (!st.isEmpty()) {
String u = st.pop();
for (String v : adj.getOrDefault(u, Collections.emptyList())) {
if (!seen.contains(v)) {
seen.add(v);
st.push(v);
}
}
}
suppressed.addAll(seen);
}
List<String> ans = new ArrayList<>();
for (String s : occur) if (!suppressed.contains(s)) ans.add(s);
Collections.sort(ans);
for (String x : ans) System.out.println(x);
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String line;
while ((line = br.readLine()) != null) {
line = line.trim();
if (line.isEmpty()) break;
String[] pn = line.split("\\s+");
int M = Integer.parseInt(pn[0]), N = Integer.parseInt(pn[1]);
List<String[]> rules = new ArrayList<>();
for (int i = 0; i < M; i++) {
String[] ab = br.readLine().trim().split("\\s+");
rules.add(new String[]{ab[0], ab[1]});
}
List<String> alerts = new ArrayList<>();
for (int i = 0; i < N; i++) alerts.add(br.readLine().trim());
solveOne(M, N, rules, alerts);
}
}
}
