CF639F Bear and Chemistry 题解

CF639F Bear and Chemistry

题意

• 给定一张 $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)$。

代码

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;
}