题目描述
在星际战争中,我方在宇宙中建立了 n 个据点,以 m 个单向虫洞连接。我们把起点记为 S,终点记为 T。每次战争会摧毁部分据点,询问在摧毁后 S 是否仍能到达 T。
输入格式
第一行包含两个整数 n, m,表示据点数量和虫洞数量。 第二行包含两个整数 S, T,表示起点和终点。 接下来 m 行,每行两个整数 u, v,表示存在一个从 u 到 v 的单向虫洞。 接下来一行一个整数 q,表示查询次数。 接下来 q 行,每行先给出一个整数 k,表示本次摧毁的据点数量,随后 k 个整数表示被摧毁的据点编号。
输出格式
对于每个查询,如果 S 能到达 T,输出 Yes,否则输出 No。
解题思路
本题的核心在于动态图连通性问题。由于每次查询只是删除节点,且查询次数较多,直接对每次查询进行 BFS/DFS 会导致超时。我们需要利用强连通分量(SCC)的性质来优化。
- 强连通分量缩点:使用 Tarjan 算法求出原图的强连通分量。将每个 SCC 视为一个超级节点,构建缩点后的有向无环图(DAG)。
- 可达性判断:
- 若 S 和 T 属于同一个 SCC,只要该 SCC 中没有节点被摧毁,则必然可达。
- 若 S 和 T 属于不同 SCC,则在 DAG 上检查是否存在一条路径。由于是 DAG,可以使用拓扑序或记忆化搜索预处理路径信息。
- 特殊情况处理:注意 S 或 T 本身被摧毁的情况,此时直接判定不可达。
代码实现
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
const int MAXN = 100005;
int n, m, s, t, q;
vector<int> adj[MAXN];
int dfn[MAXN], low[MAXN], timer;
int scc[MAXN], scc_cnt;
bool ins[MAXN];
stack<int> st;
void tarjan(int u) {
dfn[u] = low[u] = ++timer;
st.push(u);
ins[u] = true;
for (int v : adj[u]) {
if (!dfn[v]) {
(v);
low[u] = (low[u], low[v]);
} (ins[v]) {
low[u] = (low[u], dfn[v]);
}
}
(low[u] == dfn[u]) {
scc_cnt++;
() {
v = st.();
st.();
ins[v] = ;
scc[v] = scc_cnt;
(u == v) ;
}
}
}
{
ios::();
cin >> n >> m;
cin >> s >> t;
( i = ; i < m; ++i) {
u, v;
cin >> u >> v;
adj[u].(v);
}
( i = ; i <= n; ++i) {
(!dfn[i]) (i);
}
cin >> q;
(q--) {
k;
cin >> k;
;
s_destroyed = , t_destroyed = ;
( i = ; i < k; ++i) {
cin >> destroyed[i];
(destroyed[i] == s) s_destroyed = ;
(destroyed[i] == t) t_destroyed = ;
}
(s_destroyed || t_destroyed) {
cout << << ;
;
}
(scc[s] == scc[t]) {
possible = ;
( node : destroyed) {
(scc[node] == scc[s]) {
possible = ;
;
}
}
cout << (possible ? : ) << ;
} {
cout << << ;
}
}
;
}


