题解 CF639F 【Bear and Chemistry】
xht
2020-02-27 21:16:16
> [CF639F Bear and Chemistry](https://codeforces.com/contest/639/problem/F)
## 题意
- 给定一张 $n$ 个点 $m$ 条边的初始无向图。
- $q$ 次询问，每次询问给定一个点集 $V$ 和边集 $E$。
- 你需要判断，将 $E$ 中的边加入初始无向图之后，$V$ 中任意两个点 $x,y$ 是否都能**在每条边至多经过一次**的情况下从 $x$ 到 $y$ 再回到 $x$。
- $n,m,q,\sum |V|, \sum |E| \le 3 \times 10^5$，强制在线。
## 题解
两个点能来回走一次等价于这两个点在同一个边双连通分量中，因此对于单组询问，我们只需要跑一次 tarjan 就行了。
多组询问的情况下，注意到点数和边数的总数并不大，因此考虑先将初始无向图缩点成一个森林，然后对于每次询问建出虚树，再连边跑 tarjan。
设 $n,m,q,\sum |V|, \sum |E|$ 都同阶，时间复杂度为 $\mathcal O(n \log n)$。
## 代码
```cpp
const int N = 3e5 + 7, M = 6e5 + 7;
int q, rt[N], f[N][21], d[N], dfn[N], tot, s[N], t;
struct Undirected_Gragh_edcc {
int n, m, h[N], e[M*2], t[M*2], tot = 1, dfn[N], low[N], num;
bool b[M*2];
int c[N], dcc;
vi bridge, ec[N];
inline void add(int x, int y, int o = 1) {
e[++tot] = y, t[tot] = h[x], h[x] = tot;
if (o) add(y, x, 0);
}
void tarjan(int x, int f) {
dfn[x] = low[x] = ++num;
for (int i = h[x]; i; i = t[i])
if (i ^ f ^ 1) {
int y = e[i];
if (!dfn[y]) {
tarjan(y, i), low[x] = min(low[x], low[y]);
if (low[y] > dfn[x]) b[i] = b[i^1] = 1, bridge.pb(i);
} else low[x] = min(low[x], dfn[y]);
}
}
void dfs(int x) {
c[x] = dcc;
for (int i = h[x]; i; i = t[i]) {
int y = e[i];
if (c[y] || b[i]) continue;
dfs(y);
}
}
inline void Bridge() {
for (int i = 1; i <= n; i++)
if (!dfn[i]) tarjan(i, 0);
}
inline void edcc() {
Bridge();
for (int i = 1; i <= n; i++)
if (!c[i]) ++dcc, dfs(i);
}
inline void Brighe(vi p) {
for (int x : p)
if (!dfn[x]) tarjan(x, 0);
}
inline void edcc(vi p) {
Brighe(p);
for (int x : p)
if (!c[x]) ++dcc, dfs(x);
}
inline void main() {
edcc();
for (int i = 2; i <= tot; i++)
if (b[i]) ec[c[e[i]]].pb(c[e[i^1]]);
}
inline void init(vi p) {
tot = 1, num = dcc = 0;
for (int x : p) h[x] = dfn[x] = low[x] = c[x] = 0;
for (int i : bridge) b[i] = b[i^1] = 0;
bridge.clear();
}
} gragh, g;
void dfs(int x) {
dfn[x] = ++tot;
for (int y : gragh.ec[x])
if (y != f[x][0]) {
d[y] = d[x] + 1, f[y][0] = x, rt[y] = rt[x];
for (int i = 1; f[y][i-1]; i++)
f[y][i] = f[f[y][i-1]][i-1];
dfs(y);
}
}
inline int lca(int x, int y) {
if (d[x] > d[y]) swap(x, y);
for (int i = 20; ~i; i--)
if (d[f[y][i]] >= d[x]) y = f[y][i];
if (x == y) return x;
for (int i = 20; ~i; i--)
if (f[x][i] != f[y][i])
x = f[x][i], y = f[y][i];
return f[x][0];
}
inline void virtual_tree(vi &p) {
sort(p.begin(), p.end(), [](int x, int y) { return dfn[x] < dfn[y]; });
int o = 0;
vi q = p;
for (int x : p) {
if (t && rt[x] != o)
while (--t) g.add(s[t+1], s[t]);
int lca = ::lca(x, s[t]);
if (lca != s[t]) {
while (t && d[s[t-1]] >= d[lca]) g.add(s[t], s[t-1]), --t;
if (s[t] != lca) g.add(s[t], lca), s[t] = lca, q.pb(lca);
}
s[++t] = x, o = rt[x];
}
if (t) while (--t) g.add(s[t+1], s[t]);
p = q;
}
inline void work(int &x, int R) {
x = x + R > gragh.n ? x + R - gragh.n : x + R;
}
int main() {
rd(gragh.n), rd(gragh.m), rd(q);
for (int i = 1, x, y; i <= gragh.m; i++)
rd(x), rd(y), gragh.add(x, y);
gragh.main();
for (int i = 1; i <= gragh.dcc; i++)
if (!rt[i]) rt[i] = i, d[i] = 1, dfs(i);
for (int i = 1, n, m, R = 0; i <= q; i++) {
rd(n), rd(m);
vi v, p;
vector<pi> e;
for (int i = 1, x; i <= n; i++)
rd(x), work(x, R), v.pb(x = gragh.c[x]), p.pb(x);
for (int i = 1, x, y; i <= m; i++) {
rd(x), rd(y), work(x, R), work(y, R);
x = gragh.c[x], y = gragh.c[y];
if (x == y) continue;
e.pb(mp(x, y)), p.pb(x), p.pb(y);
}
sort(p.begin(), p.end());
p.erase(unique(p.begin(), p.end()), p.end());
virtual_tree(p);
for (pi o : e) g.add(o.fi, o.se);
g.edcc(p);
int k = g.c[v[0]];
bool ok = 1;
for (int x : v) if (g.c[x] != k) ok = 0;
prints(ok ? "YES" : "NO");
if (ok) R = (R + i) % gragh.n;
g.init(p);
}
return 0;
}
```