2022 CSP-S 提高组复赛真题解析：星战

题目描述

在星际战争中，我方在宇宙中建立了 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）的性质来优化。

1. 强连通分量缩点：使用 Tarjan 算法求出原图的强连通分量。将每个 SCC 视为一个超级节点，构建缩点后的有向无环图（DAG）。
2. 可达性判断：
   • 若 S 和 T 属于同一个 SCC，只要该 SCC 中没有节点被摧毁，则必然可达。
   • 若 S 和 T 属于不同 SCC，则在 DAG 上检查是否存在一条路径。由于是 DAG，可以使用拓扑序或记忆化搜索预处理路径信息。
3. 特殊情况处理：注意 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 ( v : adj[u]) {
         (!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 <<  << ;
        }
    }
     ;
}