我有一个朋友要调代码。有缘者入。我跟他无缘。
查看原帖
我有一个朋友要调代码。有缘者入。我跟他无缘。
371825
SalN楼主2023/12/14 19:54
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<iomanip>
#include<cstring>
#include<vector>
#define MAXN 200005
using namespace std;
int n,m,q,u,v,cnte=1,c[MAXN],c2[MAXN],cnt,cnt2,s[MAXN],vis[MAXN<<1],tot,up[MAXN],down[MAXN];
int dfn[MAXN],low[MAXN],head[MAXN],t,ans,depth[MAXN],fa[MAXN][22],lg[25];
vector<int>g[MAXN];
struct node{int to,nxt;}e[MAXN<<1];
void add(int u,int v){e[++cnte]=(node){v,head[u]};head[u]=cnte;}
int dfs1(int x){
	c[x]=cnt;
	for(int i=head[x];i!=-1;i=e[i].nxt)
	{int v=e[i].to;if(vis[i]||c[v])continue;dfs1(v);}
}
void Tarjan(int u,int rt){
	dfn[u]=low[u]=++t;int k=0;
	for(int i=head[u];i!=-1;i=e[i].nxt){
		int v=e[i].to;if(v==rt)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 now,int fath){
	fa[now][0]=fath;depth[now]=depth[fath]+1;c2[now]=tot;
	for(int i=1;i<=lg[depth[now]];i++)fa[now][i]=fa[fa[now][i-1]][i-1];
	for(int v:g[now]){if(v^fath)dfs(v,now);}
}
int lca(int x, int y){
	if(depth[x]<depth[y])swap(x,y);
	while(depth[x]>depth[y])
	x=fa[x][lg[depth[x]-depth[y]]-1];
	if(x==y)return x;
	for(int k=lg[depth[x]]-1;k>=0;k--)
	if(fa[x][k]!=fa[y][k])x=fa[x][k],y=fa[y][k];
	return fa[x][0];
}
bool check(int u,int fath){
	for(int v:g[u]){
		if(v==fath)continue;
		if(!check(v,u)||(up[v]&&down[v]))return false;
		up[u]+=up[v];down[u]+=down[v];
	}return true;
}
int main(){
	scanf("%d%d%d",&n,&m,&q);memset(head,-1,sizeof(head));
	for(int i=1;i<=m;i++)
	{scanf("%d%d",&u,&v);add(u,v);add(v,u);}
	for(int i=1;i<=17;i++)
	lg[i]=lg[i-1]+(1<<lg[i-1]==i);
	for(int i=1;i<=n;i++)if(!dfn[i])Tarjan(i,0);
	for(int i=1;i<=n;i++){if(!c[i])cnt++,dfs1(i);}
	for(int i=1;i<=n;i++)
		for(int j=head[i];j!=-1;j=e[j].nxt)
			{int v=e[j].to;if(c[i]<c[v]){g[c[i]].push_back(c[v]);g[c[v]].push_back(c[i]);}}
	for(int i=1;i<=cnt;i++){if(!c2[i])tot++,dfs(i,0);}
	while(q--){
		scanf("%d%d",&u,&v);
		u=c[u],v=c[v];if(u==v)continue;
		if(c2[u]!=c2[v]){return printf("No"),0;}
		int r=lca(u,v);up[u]++,up[r]--;down[v]++,down[r]--;
	}
	for(int i=1;i<=cnt;i++){
		if(!fa[i][0]&&!check(i,0))
		{return printf("No"),0;}
	}return printf("Yes"),0;
}
2023/12/14 19:54
加载中...