「CF555E」 Case of Computer Network

传送门

又是给边定向的题目（马上想到欧拉回路）

然而这个题没有对度数的限制，你想歪了。

然后又开始想一个类似于匈牙利的算法：我先跑，如果遇到要占用这条边的，我就把原来的去掉这条边试试能不能走其他路，然后这样做一遍。

这可能能够解决 \(n\) 比较小的时候的问题？

然而这题 \(n,m\le 2\times 10^5\)。

然后又想先整出他的 \(\texttt{DFS}\) 树，然后再暴力改发现完全方向错了。

事实上一个边双连通分量里存在一种定向方式使得任意两点可达。

于是我们可以缩点，然后就变成了一棵树。

一棵树就好做了，我们只需要差分覆盖，最后检查每一条边是否只有一种方向的覆盖标记即可。

贴代码

/*---Author:HenryHuang---*/

/*---Never Settle---*/

#include<bits/stdc++.h>

using namespace std;

const int maxn=4e5+5;

struct edge{

	int to,nex;

}e[maxn<<1];

int head[maxn],cnt=1;

void add(int a,int b){

	e[++cnt]=(edge){b,head[a]};

	head[a]=cnt;

}

int dfn[maxn],low[maxn],tim;

int cut[maxn<<1];

int col[maxn],num;

void tarjan(int u,int f){

	dfn[u]=low[u]=++tim;

	for(int i=head[u];i;i=e[i].nex){

		int v=e[i].to;

		if(!dfn[v]){

			tarjan(v,u);

			low[u]=min(low[u],low[v]);

			if(low[v]>dfn[u]) cut[i]=cut[i^1]=1;

		}

		else if(v!=f) low[u]=min(low[u],dfn[v]);

	}

}

void dfs2(int u){

	col[u]=num;

	for(int i=head[u];i;i=e[i].nex){

		int v=e[i].to;

		if(col[v]||cut[i]) continue;

		dfs2(v);

	}

}

vector<int> t[maxn];

int dep[maxn],siz[maxn],son[maxn],top[maxn],fa[maxn],tag[maxn],id;

void dfs3(int u,int f){

	fa[u]=f;dep[u]=dep[f]+1;

	siz[u]=1;tag[u]=id;

	for(auto v:t[u]){

		if(v==f) continue;

		dfs3(v,u);

		siz[u]+=siz[v];

		if(siz[son[u]]<siz[v]) son[u]=v;

	}

}

void dfs4(int u,int f){

	top[u]=f;

	if(son[u]) dfs4(son[u],f);

	for(auto v:t[u]){

		if(v==fa[u]||v==son[u]) continue;

		dfs4(v,v);

	}

}

int lca(int x,int y){

	while(top[x]!=top[y]){

		if(dep[top[x]]>=dep[top[y]]) x=fa[top[x]];

		else y=fa[top[y]];

	}

	return dep[x]<dep[y]?x:y;

}

int up[maxn],down[maxn];

bool dfs5(int u,int f){

	for(auto v:t[u]){

		if(v==f) continue;

		if(!dfs5(v,u)||(up[v]&&down[v])) return 0;

		up[u]+=up[v],down[u]+=down[v];

	}

	return 1;

}

int main(){

	ios::sync_with_stdio(0);

	cin.tie(0),cout.tie(0);

	int n,m,q;cin>>n>>m>>q;

	for(int i=1;i<=m;++i){

		int a,b;cin>>a>>b;

		add(a,b),add(b,a);

	}

	for(int i=1;i<=n;++i)

		if(!dfn[i]) tarjan(i,0);

	for(int i=1;i<=n;++i)

		if(!col[i]) ++num,dfs2(i);

	for(int u=1;u<=n;++u)

		for(int i=head[u];i;i=e[i].nex){

			int v=e[i].to;

			if(col[u]<col[v]){

				t[col[u]].emplace_back(col[v]);

				t[col[v]].emplace_back(col[u]);

			}

		}

	for(int i=1;i<=num;++i)

		if(!tag[i]) ++id,dfs3(i,0),dfs4(i,i);

	for(int i=1;i<=q;++i){

		int a,b;cin>>a>>b;

		a=col[a],b=col[b];

		if(tag[a]!=tag[b]){

			cout<<"No\n";

			return 0;

		}

		int c=lca(a,b);

		++up[a],--up[c];

		++down[b],--down[c];

	}

	for(int i=1;i<=num;++i)

		if(fa[i]==0&&(!dfs5(i,0))){

			cout<<"No\n";

			return 0;

		}

	cout<<"Yes\n";

	return 0;

}

巴特西

「CF555E」 Case of Computer Network

「CF555E」 Case of Computer Network

最新文章

热门文章