CF555E Case of Computer Network 题解

CF555E Case of Computer Network

题意

• 给定一张 $n$ 个点 $m$ 条边的无向图。
• 给定 $q$ 组有向点对 $(s, t)$。
• 询问是否存在使得所有 $s$ 都能到达 $t$ 的无向图中每条边的定向方案。
• $n,m,q \le 2 \times 10^5$。

题解

先求边双，缩点变成森林。

判定时先求 lca，树上差分一下即可，时间复杂度 $\mathcal O(n \log n)$。

代码

const int N = 2e5 + 7;
int n, m, q;
int h[N], e[N<<1], t[N<<1], p = 1;
int dfn[N], low[N], num;
int b[N<<1], c[N], k;
int hc[N], ec[N<<1], tc[N<<1], pc = 1;
int v[N], w, f[N][20], d[N], g1[N], g2[N];

inline void add(int x, int y, int z = 1) {
	e[++p] = y;
	t[p] = h[x];
	h[x] = p;
	if (z) 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) continue;
		int y = e[i];
		if (dfn[y]) low[x] = min(low[x], dfn[y]);
		else {
			tarjan(y, i ^ 1), low[x] = min(low[x], low[y]);
			if (low[y] > dfn[x]) b[i] = b[i^1] = 1;
		}
	}
}

void dfs(int x) {
	c[x] = k;
	for (int i = h[x]; i; i = t[i]) {
		if (b[i]) continue;
		int y = e[i];
		if (c[y]) continue;
		dfs(y);
	}
}

inline void addc(int x, int y, int z = 1) {
	ec[++pc] = y;
	tc[pc] = hc[x];
	hc[x] = pc;
	if (z) addc(y, x, 0);
}

void dfsc(int x) {
	v[x] = w;
	for (int i = hc[x]; i; i = tc[i]) {
		int y = ec[i];
		if (y == f[x][0]) continue;
		f[y][0] = x, d[y] = d[x] + 1;
		for (int j = 0; f[y][j]; j++)
			f[y][j+1] = f[f[y][j]][j];
		dfsc(y);
	}
}

inline int lca(int x, int y) {
	if (d[x] > d[y]) swap(x, y);
	for (int i = 19; ~i; i--)
		if (d[f[y][i]] >= d[x]) y = f[y][i];
	if (x == y) return x;
	for (int i = 19; ~i; i--)
		if (f[x][i] ^ f[y][i]) x = f[x][i], y = f[y][i];
	return f[x][0];
}

bool dfspd(int x) {
	for (int i = hc[x]; i; i = tc[i]) {
		int y = ec[i];
		if (y == f[x][0]) continue;
		if (!dfspd(y) || (g1[y] && g2[y])) return 0;
		g1[x] += g1[y], g2[x] += g2[y];
	}
	return 1;
}

int main() {
	rd(n), rd(m), rd(q);
	for (int i = 1, x, y; i <= m; i++)
		rd(x), rd(y), add(x, y);
	for (int i = 1; i <= n; i++)
		if (!dfn[i]) tarjan(i, 0);
	for (int i = 1; i <= n; i++)
		if (!c[i]) ++k, dfs(i);
	for (int x = 1; x <= n; x++)
		for (int i = h[x]; i; i = t[i]) {
			int y = e[i];
			if (c[x] >= c[y]) continue;
			addc(c[x], c[y]);
		}
	for (int i = 1; i <= k; i++)
		if (!v[i]) ++w, d[i] = 1, dfsc(i);
	for (int i = 1, x, y; i <= q; i++) {
		rd(x), rd(y), x = c[x], y = c[y];
		if (x == y) continue;
		if (v[x] != v[y]) return prints("No"), 0;
		int z = lca(x, y);
		++g1[x], --g1[z], ++g2[y], --g2[z];
	}
	for (int i = 1; i <= n; i++)
		if (d[i] == 1 && !dfspd(i)) return prints("No"), 0;
	prints("Yes");
	return 0;
}