CF555E Case of Computer Network

IOI2020集训队作业

腾个题面,先咕着

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

我们考虑现在原图上处理一下...如果能得到一个简化后的问题我们就能做了!

比如?树上问题,如果这个是一颗树,能不能满足这些限制就是一个树上差分类似的统计就行了

而一般图变成树?又和连通性有关?仙人掌?圆方树?好像都行??/惊恐

当然我们不需要那么复杂的缩点,只需要缩边双就好啦!

为啥呢?首先我们缩了边双后图成为一棵树....而且同一个点内一定满足有一种合法的安排边的方法能使条件满足!

因为如是一个环我们就都朝某个方向就一定可以

最后树上统计只需要看一条边是否有被要求向上同时向下就好

code:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define CT const int &
#define min(x,y) ((x)<(y)?(x):(y))
namespace fastIO {
#define BUF_SIZE (1<<19)
	static char buf[BUF_SIZE], *p1 = buf + BUF_SIZE, *pend = buf + BUF_SIZE;
	inline char nc() {
		if(p1 == pend) {
			p1 = buf;
			pend = buf + fread(buf, 1, BUF_SIZE, stdin);
		}
		return *p1++;
	}

	inline int read() {
		int x = 0, f = 1;
		register char s = nc();
		for(; !isdigit(s); s = nc())if(s == '-')f = -1;
		for(; isdigit(s); s = nc())x = (x << 1) + (x << 3) + s - '0';
		return x * f;
	}
#undef BUF_SIZE
}
using namespace fastIO;

const int MAXN = 4e5 + 9;

int home[MAXN], nxt[MAXN], to[MAXN], st[MAXN], first[MAXN], ccnt = 1, cccnt = 1;
int col[MAXN], dfn[MAXN], low[MAXN], num, son[MAXN],
	fa[MAXN], siz[MAXN], top[MAXN], dep[MAXN], tot,
	bel[MAXN], ins[MAXN], tp, frm[MAXN];

struct edge {
	int nxt, to;
} e[MAXN];

inline void ct1(CT x, CT y) {
	++ccnt;
	nxt[ccnt] = home[x];
	home[x] = ccnt;
	to[ccnt] = y;
	frm[ccnt] = x;
}

inline void ct2(CT x, CT y) {
	++cccnt;
	e[cccnt].to = y;
	e[cccnt].nxt = first[x];
	first[x] = cccnt;
}

void tarjan(int u, int fr) {
	dfn[u] = low[u] = ++num;
	col[u] = col[0];
	st[++tp] = u, ins[u] = 1;
	///printf("%d? %d\n", u, fr);
	for(int i = home[u]; i; i = nxt[i]) {
		int v = to[i];
		if((i ^ 1) == fr)continue;
		if(!dfn[v]) {
			tarjan(v, i);
			low[u] = min(low[u], low[v]);
		} else if(ins[v])low[u] = min(dfn[v], low[u]);
	}
	if(dfn[u] == low[u]) {
		int v = 0;
		++tot;
		while(v != u) {
			v = st[tp];
			--tp;
			bel[v] = tot;
			ins[v] = 0;
		}
	}
}

inline void dfs1(int u, int F) {
	dep[u] = dep[F] + 1;
	fa[u] = F;
	siz[u] = 1;
	//printf("%d! %d\n", u, F);

	for(int i = first[u]; i; i = e[i].nxt) {
		int v = e[i].to;
		if(v == F)continue;
		dfs1(v, u);
		siz[u] += siz[v];
		if(siz[v] > siz[son[u]])son[u] = v;
	}
}

inline void dfs2(int u, int topf) {
	top[u] = topf;
	//printf("%d %d\n", u, topf);
	if(son[u])dfs2(son[u], topf);
	for(int i = first[u]; i; i = e[i].nxt) {
		int v = e[i].to;
		if(v == fa[u] || v == son[u])continue;
		dfs2(v, v);
	}

}
#define swap(x,y) (x^=y^=x^=y)
inline int LCA(int x, int y) {
	while(top[x] != top[y]) {
		//printf("%d %d\n", x, y);
		if(dep[top[x]] < dep[top[y]])swap(x, y);
		x = fa[top[x]];
	}
	return dep[x] < dep[y] ? x : y;
}

int up[MAXN], down[MAXN], tag[MAXN];

inline void dfs3(int u) {
	tag[u] = 1;
	//printf("%d?\n", u);
	for(int i = first[u]; i; i = e[i].nxt) {
		int v = e[i].to;
		if(v == fa[u])continue;
		dfs3(v);
		up[u] += up[v];
		down[u] += down[v];
	}
}

int n, m, q;

int main() {
	//freopen("test.in", "r", stdin);
	n = read();
	m = read();
	q = read();
	for(register int i = 1, x, y; i <= m; ++i) {
		x = read();
		y = read();
		ct1(x, y);
		ct1(y, x);
	}
	//puts("Qwqw");
	for(register int i = 1; i <= n; ++i) {
		if(!dfn[i]) {
			col[0]++;
			tarjan(i, 0);
		}
	}
	for(register int i = 2; i <= ccnt; i += 2) {
		int x = frm[i];
		int y = to[i];
		//printf("%d %d\n", x, y);
		if(bel[x] == bel[y])continue;
		ct2(bel[x], bel[y]);
		ct2(bel[y], bel[x]);
	}
	for(register int i = 1; i <= n; ++i) {
		if(!dep[i]) {
			dfs1(i, 0);
			dfs2(i, i);
		}
	}
	// for(int i = 1; i <= n; ++i) {
	// 	printf("%d %d %d %d\n", i, dep[i], fa[i], siz[i]);
	// }
	for(register int x, y, i = 1; i <= q; ++i) {
		x = read();
		y = read();
		if(col[x] != col[y])return puts("No"), 0;
		x = bel[x], y = bel[y];
		int anc = LCA(x, y);
		up[x]++;
		up[anc]--;
		down[y]++;
		down[anc]--;
	}
	for(register int i = 1; i <= n; ++i)if(!tag[i])dfs3(i);
	for(register int i = 1; i <= n; ++i) {
		if(up[i] && down[i]) {
			return puts("No"), 0;
		}
	}
	return 	puts("Yes"), 0;
}

夏晓光(loveJY)的博客

CF521D Shop