题意
给定一张有向图，问你反转一条边后是否对 \(scc\) 有变化。
\(n \le 1500, m \le 10^6\)
Sol
先对图跑一边 \(tarjan\)，考虑对每条边进行分讨。
- 在同一强连通分量里。如果反转后依然有一条 \(u \to v\) 的路径，那么 \(scc\) 不变，否则变多。
- 在 \(DAG\) 的边上。如果反转后依然有一条 \(u \to v\) 的路径，\(scc\) 变少，因为 \(u \to v\) 将两个 \(scc\) 连起来了，否则不变。
所以，问题转为询问 \(u \to v\) 的边去掉后是否有一条 \(u \to v\) 的路径。
直接暴力 \(bfs\) 固然是 \(O(m \times (n + m))\) 的。
注意到 \(n\) 很小，所以想到用 \(bitset\) 优化 \(bfs\) 求两点联通性。
我们设 \(g_u\) 表示 \(u\) 能到达的所有节点。
考虑 \(u\) 的所有出点，设为 \(V_i\)。
不难发现当前 \(u, v\) 联通，当且仅当存在一个 \(V_i\) 有一条 \(V_i \to v\) 的路径，那么求答案就变为求一个 \([V_1, V_{i - 1}]\) 的前缀，以及 \([V_{i + 1}, V_{|V|}]\) 的后缀的 \(g\) 全部或起来。
那么每次跑 \(bfs\) 就不需要全部清空了，直接暴力加点跑就行。
\(bfs\) 的复杂度为 \(\frac{n ^ 2}{\omega}\)。
每个点的所有出点跑一次 \(bfs\)。
总时间复杂度：\(O(\frac{n ^ 3}{\omega} + \frac{n \times m}{\omega})\)
Code
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <array>
#include <stack>
#include <queue>
#include <bitset>
#include <vector>
#define pii pair <int, int>
using namespace std;
#ifdef ONLINE_JUDGE
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
char buf[1 << 23], *p1 = buf, *p2 = buf, ubuf[1 << 23], *u = ubuf;
#endif
int read() {
int p = 0, flg = 1;
char c = getchar();
while (c < '0' || c > '9') {
if (c == '-') flg = -1;
c = getchar();
}
while (c >= '0' && c <= '9') {
p = p * 10 + c - '0';
c = getchar();
}
return p * flg;
}
void write(int x) {
if (x < 0) {
x = -x;
putchar('-');
}
if (x > 9) {
write(x / 10);
}
putchar(x % 10 + '0');
}
#define fi first
#define se second
const int N = 1505, M = 1e6 + 5;
namespace G {
array <int, N> fir;
array <int, M> nex, to, len;
int cnt = 1;
void add(int x, int y, int z) {
cnt++;
nex[cnt] = fir[x];
to[cnt] = y;
len[cnt] = z;
fir[x] = cnt;
}
}
namespace Tarjan {
array <int, N> dfn, low;
bitset <N> mark, vis;
stack <int> stk;
int cnt = 1, scc = 0;
array <int, N> col;
void tarjan(int x) {
dfn[x] = low[x] = cnt++;
stk.push(x);
mark[x] = vis[x] = 1;
for (int i = G::fir[x]; i; i = G::nex[i]) {
if (!dfn[G::to[i]])
tarjan(G::to[i]), low[x] = min(low[x], low[G::to[i]]);
else if (mark[G::to[i]])
low[x] = min(low[x], dfn[G::to[i]]);
}
if (dfn[x] != low[x]) return;
scc++;
while (stk.top() != x) {
col[stk.top()] = scc;
mark[stk.top()] = 0;
stk.pop();
}
col[stk.top()] = scc;
mark[stk.top()] = 0;
stk.pop();
}
}
array <bitset <N>, N> f, g;
bitset <N> vis, tp;
queue <int> q;
void bfs(int x, int n) {
while (!q.empty()) {
int u = q.front();
q.pop();
if (u == x) continue;
tp = (g[u] & vis) ^ g[u];
for (int i = tp._Find_first(); i <= n; i = tp._Find_next(i))
vis[i] = 1, q.push(i);
}
}
bitset <N * N> ans;
vector <pii> isl;
int main() {
/* freopen("scc.in", "r", stdin); */
/* freopen("scc.out", "w", stdout); */
int n = read(), m = read();
for (int i = 1; i <= m; i++) {
int x = read(), y = read();
G::add(x, y, i), g[x][y] = 1;
}
for (int i = 1; i <= n; i++)
if (!Tarjan::dfn[i]) Tarjan::tarjan(i);
/* for (int i = 1; i <= n; i++) */
/* write(Tarjan::col[i]), putchar(32); */
/* puts(""); */
for (int i = 1; i <= n; i++) {
vis = 0;
isl.clear();
for (int j = G::fir[i]; j; j = G::nex[j])
isl.push_back(make_pair(G::to[j], G::len[j]));
for (int j = 0; j < (int)isl.size(); j++) {
if (!vis[isl[j].fi]) q.push(isl[j].fi), bfs(i, n), f[j + 1] = vis;
else f[j + 1] = f[j];
}
vis = 0;
for (int j = isl.size() - 1; ~j; j--) {
ans[isl[j].se] = (vis.test(isl[j].fi) | f[j].test(isl[j].fi)) ^ (Tarjan::col[i] == Tarjan::col[isl[j].fi]);
if (!vis[isl[j].fi]) q.push(isl[j].fi), bfs(i, n);
}
}
for (int i = 1; i <= m; i++)
write(ans[i]), puts("");
return 0;
}