UVa 11896 Inglorious Gangs

题目描述

在罪恶都市中，帮派以车队形式在街道上行驶。警察数量不足，只能由一名警察追捕一个帮派车队。当车队到达某个交叉路口时，每辆帮派车辆会分别驶向不同的方向，使落单的警察困惑，帮派从而逃脱。警方知道，帮派车队只有在能够于城市中某处重新集结的情况下才会分开。他们计划封锁部分道路，防止车队分开，从而让警察能一直追捕直到抓住他们。

城市地图是有向图，节点表示交叉路口，有向边表示道路。你需要判断在给定的未封锁道路下，是否已经能够困住帮派。如果能困住，输出 Trapped，否则输出 Not Trapped。

形式化地说：判断有向图中是否存在两个不同的顶点 $u$ 和 $v$，使得从 $u$ 到 $v$ 存在两条边不相交的路径（即路径间没有共享的有向边，但可以共享顶点）。若存在，帮派可在 $u$ 处分叉，并在 $v$ 处重新集结，从而逃脱。

输入格式

第一行一个整数 $T$（$T\le 100$），表示测试用例数量。

每个测试用例以两个整数 $N$ 和 $M$ 开头（$1\le N\le 5000$，$M\le 10^5$），分别表示交叉路口的数量和未封锁道路的数量。

接下来 $M$ 行，每行两个整数 $u$ $v$（$1\le u,v\le N$，$u\ne v$），表示存在一条从 $u$ 到 $v$ 的有向道路。

保证没有自环，但可能存在平行边。

输出格式

对于每个测试用例，输出一行：若能够困住帮派，打印 Trapped；否则打印 Not Trapped。

样例

输入

2
3 3
1 2
2 3
1 3
4 4
1 2
2 3
3 4
4 2

输出

Not Trapped
Trapped

解释：

• 第一组：从 $1$ 有两条边分别到 $2$ 和 $3$，而 $2$ 又能到达 $3$，帮派可在 $1$ 分叉，在 $3$ 汇合，存在边不相交路径。
• 第二组：唯一的环是 $2\to 3\to 4\to 2$，从 $1$ 出发只有一条路径进入该环，无法分叉后重聚，因此困住。

题目分析

本题的本质是判断有向图中是否存在两条边不相交的路径。根据 $\text{Menger}$ 定理（边连通度版本），两点 $u$ 到 $v$ 存在两条边不相交路径等价于它们之间的边连通度至少为 $2$，在网络流中表现为最大流不小于 $2$（每条边容量为 $1$）。但直接对每一对出度 $\ge 2$ 的节点跑最大流，复杂度高达 $O(N\cdot M\cdot \sqrt{N})$，无法承受 $N\le 5000$ 的规模。

我们需要更高效的方法。观察图的结构：

• 强连通分量（$\text{SCC}$）内部：若一个大小至少为 $2$ 的 $\text{SCC}$ 中某个顶点有两条边指向同一 $\text{SCC}$ 内的其他顶点，则由于强连通性，这两条边出发的路径必然能在该 $\text{SCC}$ 内某处汇合，从而形成边不相交路径。
• 跨 $\text{SCC}$：缩点后得到有向无环图（$\text{DAG}$）。在 $\text{DAG}$ 中，若一个 $\text{SCC}$ 的出度至少为 $2$，且存在两条不同的出边指向的 $\text{SCC}$，它们的“可达 $\text{SCC}$ 集合”有交集，则最早的交汇 $\text{SCC}$ 处一定存在边不相交的路径（因为不同分支首次汇合时，进入该 $\text{SCC}$ 的边必然不同）。

关键转化：我们不需要精确找到汇合顶点，只需在 $\text{DAG}$ 中检查可达集的交集即可。

解题思路

第一步：强连通分量缩点

使用 $\text{Tarjan}$ 算法求出所有 $\text{SCC}$，并记录每个顶点所属的 $\text{SCC}$ 编号 $c_u$，以及每个 $\text{SCC}$ 的大小 $sz[c]$。

统计每个顶点 $u$ 在原图中，连向同一 $\text{SCC}$ 的出边数量 $\text{innerOut}[u]$。

第二步：$\text{SCC}$ 内部快速判定

遍历每个大小 $\ge 2$ 的 $\text{SCC}$，若其中存在某个顶点 $u$ 满足 $\text{innerOut}[u]\ge 2$，则直接判定存在边不相交路径（帮派可逃脱）。因为 $u$ 有两条边留在 $\text{SCC}$ 内部，强连通性保证这两条路径可以汇合。

第三步：构建 $\text{DAG}$ 并计算可达集

忽略 $\text{SCC}$ 内部的边，将每个 $\text{SCC}$ 视为一个超级节点，建立 $\text{DAG}$。同时统计每个 $\text{SCC}$ 的出度 $d_{\text{out}}[c]$。

对 $\text{DAG}$ 进行拓扑排序，按拓扑逆序计算每个 $\text{SCC}$ 的可达集合 $R[c]$，用一个 $\text{bitset}$ 存储（因为 $N\le 5000$，$\text{bitset}$ 仅需约 $625$ 字节，快速且空间充足）。

$$R[c]=\{c\}\cup \bigcup _{v\in \text{dag}[c]}R[v]$$

第四步：$\text{DAG}$ 中判定

对于每个出度 $\ge 2$ 的 $\text{SCC}$ $c$，依次检查它的所有出边邻居对应的 $R$：

• 维护一个 $\text{bitset}$ $\text{seen}$，表示已遍历过的邻居的可达集之并。
• 若当前邻居的 $R$ 与 $\text{seen}$ 有交集，则说明存在两条不同的出边，它们的可达集有重叠，从而存在边不相交路径。
• 若有交集，直接判定可逃脱。

若所有检查均未发现，则输出 Trapped。

正确性证明

• 内部判定：若 $u$ 在 $\text{SCC}$ 内部有至少两条出边，设指向 $x$ 和 $y$。由于 $\text{SCC}$ 强连通，存在 $x⇝y$ 或 $y⇝u$ 等路径，结合 $u$ 的出边，总能构造出两条边不相交的路径到达 $\text{SCC}$ 内某顶点（如 $x$ 自身或经由环回到 $u$ 等）。
• 跨 $\text{SCC}$ 判定：设 $c$ 有两条出边分别到 $p$ 和 $q$，且 $R[p]\cap R[q]\ne \varnothing$。取交集中的一个 $\text{SCC}$ $w$，则从 $p$ 到 $w$ 和从 $q$ 到 $w$ 的路径在 $\text{DAG}$ 中不会共享边（因为 $p\ne q$），且两条路径进入 $w$ 的边必不同（否则它们会在更早的 $\text{SCC}$ 就汇合，与“最早交集”矛盾）。因此，原图中存在从某个 $u\in c$ 出发，经过不同边到达 $w$ 中某顶点的两条边不相交路径。

复杂度分析

• $\text{Tarjan}$ 缩点：$O(N+M)$
• 构建 $\text{DAG}$ 与拓扑排序：$O(N+M)$
• 计算可达集：共 $O(N)$ 个 $\text{bitset}$，每个大小为 $N/64$，合并在拓扑序下总时间为 $O(N\cdot (N/64))\approx 4\times 10^5$ 次位运算，非常快。
• 交集判定：每个 $\text{SCC}$ 最多遍历其出边，总位运算次数 $O(M\cdot (N/64))$ 也在合理范围内。
• 总时间复杂度：$O(N^2/64+M)$，空间复杂度：$O(N^2/64+M)$，均可通过。

代码实现

// Inglorious Gangs
// UVa ID: 11896
// Verdict: Accepted
// Submission Date: 2026-06-22
// UVa Run Time: 0.370s
//
// 版权所有（C）2026，邱秋。metaphysis # yeah dot net

#include <bits/stdc++.h>
using namespace std;

void solve() {
ios::sync_with_stdio(false); cin.tie(nullptr);
int T; cin >> T;
while (T—) {
int N, M; cin >> N >> M;
vector<vector<int>> g(N + 1);
vector<int> od(N + 1), id(N + 1);
bool parallel = false;
unordered_set<long long> E;
for (int i = 0; i < M; ++i) {
int u, v; cin >> u >> v;
g[u].push_back(v);
od[u]++; id[v]++;
long long key = 1LL * u * (N + 1) + v;
if (!E.insert(key).second) parallel = true;
}
if (parallel) { cout << "Not Trapped\\n"; continue; }

// Tarjan算法缩点
vector<int> dfn(N + 1), low(N + 1), comp(N + 1);
vector<bool> inSt(N + 1);
stack<int> st;
int tm = 0, sc = 0;
function<void(int)> dfs = [&](int u) {
dfn[u] = low[u] = ++tm;
st.push(u); inSt[u] = true;
for (int v : g[u]) {
if (!dfn[v]) {
dfs(v);
low[u] = min(low[u], low[v]);
} else if (inSt[v]) low[u] = min(low[u], dfn[v]);
}
if (low[u] == dfn[u]) {
++sc;
int v;
do {
v = st.top(); st.pop();
inSt[v] = false;
comp[v] = sc;
} while (v != u);
}
};
for (int i = 1; i <= N; ++i) if (!dfn[i]) dfs(i);

// SCC 内部出度与大小
vector<int> innerOut(N + 1), sz(sc + 1);
for (int i = 1; i <= N; ++i) sz[comp[i]]++;
for (int u = 1; u <= N; ++u)
for (int v : g[u])
if (comp[u] == comp[v]) innerOut[u]++;

bool escaped = false;
for (int c = 1; c <= sc && !escaped; ++c) {
if (sz[c] < 2) continue;
for (int u = 1; u <= N; ++u)
if (comp[u] == c && innerOut[u] >= 2) { escaped = true; break; }
}
if (escaped) { cout << "Not Trapped\\n"; continue; }

// 检查原图中节点出度>=2且两条边进入同一个大小>=2的SCC
for (int u = 1; u <= N && !escaped; ++u) {
if (od[u] < 2) continue;
unordered_set<int> seenSCC;
for (int v : g[u]) {
int c = comp[v];
if (sz[c] >= 2 && !seenSCC.insert(c).second) { escaped = true; break; }
}
}
if (escaped) { cout << "Not Trapped\\n"; continue; }

// 缩点 DAG
vector<vector<int>> dag(sc + 1);
vector<int> dout(sc + 1), din(sc + 1);
vector<unordered_set<int>> tmp(sc + 1);
for (int u = 1; u <= N; ++u)
for (int v : g[u])
if (comp[u] != comp[v])
if (tmp[comp[u]].insert(comp[v]).second) {
dag[comp[u]].push_back(comp[v]);
dout[comp[u]]++;
din[comp[v]]++;
}

// 拓扑排序
vector<int> tp;
queue<int> q;
for (int i = 1; i <= sc; ++i) if (din[i] == 0) q.push(i);
while (!q.empty()) {
int u = q.front(); q.pop();
tp.push_back(u);
for (int v : dag[u]) if (—din[v] == 0) q.push(v);
}

// 计算每个SCC的可达集
vector<bitset<5005>> R(sc + 1);
for (auto it = tp.rbegin(); it != tp.rend(); ++it) {
int u = *it;
R[u].set(u);
for (int v : dag[u]) R[u] |= R[v];
}

// DAG中出度>=2的SCC检查可达集交集
for (int c = 1; c <= sc && !escaped; ++c) {
if (dout[c] < 2) continue;
bitset<5005> seen;
for (int v : dag[c]) {
if ((seen & R[v]).any()) { escaped = true; break; }
seen |= R[v];
}
}

cout << (escaped ? "Not Trapped" : "Trapped") << '\\n';
}
}

int main() { solve(); return 0; }

总结

本题巧妙地将“边不相交路径”的判定转化为可达集交集的问题，避免了耗时的最大流计算。核心技巧在于：

该解法充分利用了图的结构性质和位运算加速，是 $\text{SCC}$ 缩点与 $\text{bitset}$ 优化的经典应用。