脚本宝典收集整理的这篇文章主要介绍了[作业题] #5 CF555E &，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

Case of Computer Network

题目描述

点此看题

解法

显然本题是一个边双连通分量版题，缩点之后树上差分定向即可。由于我以前没有怎么写过点双和边双，所以我的主要目的是把它们总结一下。

点双：在强连通分量的基础上，不在回溯的时候染色，而是在访问完某个儿子之后立即判断 low[v]>=dfn[u]，如果是的话就立即划分点双连通分量，并且把 (u) 这个点也放进连通分量中。并且如果根只有一个儿子需要特判，此时根不是割点。

边双：在 (tt tarjan) 的时候不进行染色，只是回溯时对于满足 low[v]>dfn[u] 的边设置为不可访问的。然后暴力 (tt dfs)，每次将访问到的点全部设置为同一个边双，不需要任何特判。

#include <cstdio>
#include <vector>
#include <cstdlib>
#include <iostream>
using namespace std;
const int M = 200005;
int read()
{
	int x=0,f=1;char c;
	while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
	while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
int n,m,k,tot,f[M],vis[M<<1],col[M],bl[M],dep[M];
int t,cnt,dfn[M],low[M],a[M],b[M],fa[M][20];
struct edge{int v,next;}e[M<<1];vector<int> g[M];
void tarjan(int u,int fa)
{
	dfn[u]=low[u]=++cnt;
	for(int i=f[u];i;i=e[i].next)
	{
		int v=e[i].v;
		if(v==fa) continue;
		if(!dfn[v])
		{
			tarjan(v,u);
			low[u]=min(low[u],low[v]);
			if(low[v]>dfn[u])
				vis[i]=vis[i^1]=1;
		}
		else low[u]=min(low[u],dfn[v]);
	}
}
void dfs(int u,int c)
{
	col[u]=c;
	for(int i=f[u];i;i=e[i].next)
	{
		int v=e[i].v;
		if(col[v] || vis[i]) continue;
		dfs(v,c);
	}
}
void pre(int u,int p)
{
	bl[u]=bl[p];fa[u][0]=p;
	dep[u]=dep[p]+1; 
	for(int i=1;i<20;i++)
		fa[u][i]=fa[fa[u][i-1]][i-1];
	for(int v:g[u]) if(v^p)
		pre(v,u);
}
int lca(int u,int v)
{
	if(dep[u]<dep[v]) swap(u,v);
	for(int i=19;i>=0;i--)
		if(dep[fa[u][i]]>=dep[v])
			u=fa[u][i];
	if(u==v) return u;
	for(int i=19;i>=0;i--)
		if(fa[u][i]^fa[v][i])
			u=fa[u][i],v=fa[v][i];
	return fa[u][0];
}
void pd(int u)
{
	for(int v:g[u]) if(v^fa[u][0])
		pd(v),a[u]+=a[v],b[u]+=b[v];
	if(a[u] && b[u]) {puts("No");exit(0);}
}
signed main()
{
	n=read();m=read();k=read();tot=1;
	for(int i=1;i<=m;i++)
	{
		int u=read(),v=read();
		e[++tot]=edge{u,f[v]},f[v]=tot;
		e[++tot]=edge{v,f[u]},f[u]=tot;
	}
	for(int i=1;i<=n;i++)
		if(!dfn[i]) tarjan(i,0);
	for(int i=1;i<=n;i++)
		if(!col[i]) dfs(i,col[i]=++t);
	for(int u=1;u<=n;u++)
		for(int i=f[u];i;i=e[i].next)
		{
			int v=e[i].v;
			if(col[u]<col[v])
			{
				g[col[u]].push_back(col[v]);
				g[col[v]].push_back(col[u]);
			}
		}
	for(int i=1;i<=t;i++)
		if(!bl[i]) bl[0]=i,pre(i,0);
	while(k--)
	{
		int u=col[read()],v=col[read()];
		if(bl[u]!=bl[v])
		{
			puts("No");
			return 0;
		}
		if(u==v) continue;
		int x=lca(u,v);
		a[u]++;a[x]--;b[v]++;b[x]--;
	}
	for(int i=1;i<=t;i++)
		if(!fa[i][0]) pd(i);
	puts("Yes");
}

脚本宝典总结

以上是脚本宝典为你收集整理的[作业题] #5 CF555E &全部内容，希望文章能够帮你解决[作业题] #5 CF555E &所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。