WA on#9求调(
查看原帖
WA on#9求调(
743048
ran_qwq楼主2024/1/22 07:58
#include<bits/stdc++.h>
#define ui unsigned int
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fir first
#define sec second
#define mem(arr,val) memset(arr,val,sizeof arr)
#define vi vector<int>
#define pb push_back
#define gi greater<int>
#define pq priority_queue
using namespace std;
const int N=2e5+10,INF=0x3f3f3f3f;
namespace FIO
{
	int read() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();return x*f;}
	void Write(int x) {if(x<0) {putchar('-'),Write(-x);return;}if(x<10) {putchar(x+'0');return;}Write(x/10),putchar(x%10+'0');}
	void write(int x,char *s) {Write(x),printf("%s",s);}
}using namespace FIO;
int n,m,k,id=1,idx,cnt,tot,to[N<<1],ne[N<<1],head[N],dfn[N],low[N],vis[N],col[N],num[N],dep[N],c[N],d[N],st[N][20];
vi G[N];
void add(int x,int y) {to[++id]=y,ne[id]=head[x],head[x]=id;}
void dfs1(int u,int lst)
{
	dfn[u]=low[u]=++idx;
	for(int i=head[u];i;i=ne[i])
	{
		int v=to[i];
		if(!dfn[v])
		{
			dfs1(v,i^1),low[u]=min(low[u],low[v]);
			if(dfn[u]<low[v]) vis[i]=vis[i^1]=1;
		}
		else if(i!=lst) low[u]=min(low[u],dfn[v]);
	}
}
void dfs2(int u)
{
	col[u]=tot;
	for(int i=head[u];i;i=ne[i])
		if(!col[to[i]]&&!vis[i]) dfs2(to[i]);
}
void dfs3(int u,int fa)
{
	num[u]=tot,dep[u]=dep[fa]+1,st[u][0]=fa;
	for(int i=1;i<=19;i++) st[u][i]=st[st[u][i-1]][i-1];
	for(int v:G[u])
		if(v!=fa) dfs3(v,u);
}
int LCA(int x,int y)
{
	if(dep[x]<dep[y]) swap(x,y);
	for(int i=19;~i;i--)
		if(dep[st[x][i]]>=dep[y]) x=st[x][i];
	return x;
	for(int i=19;~i;i--)
		if(st[x][i]!=st[y][i]) x=st[x][i],y=st[y][i];
	return st[x][0];
}
bool dfs4(int u,int fa)
{
	for(int v:G[u])
		if(v!=fa)
		{
			if(!dfs4(v,u)||c[v]&&d[v]) return 0;
			c[u]+=c[v],d[u]+=d[v]; 
		}
	return 1;
}
void solve()
{
	n=read(),m=read(),k=read();
	for(int i=1,x,y;i<=m;i++) x=read(),y=read(),add(x,y),add(y,x);
	for(int i=1;i<=n;i++)
		if(!dfn[i]) dfs1(i,0);
	for(int i=1;i<=n;i++)
		if(!col[i]) tot++,dfs2(i);
	for(int i=1;i<=n;i++)
		for(int j=head[i];j;j=ne[j])
			if(col[i]!=col[to[j]]) G[col[i]].pb(col[to[j]]);
	for(int i=1;i<=tot;i++)
		if(!num[i]) cnt++,dfs3(i,0);
	for(int i=1,x,y,p;k--;)
	{
		x=col[read()],y=col[read()],p=LCA(x,y);
		if(x==y) continue;
		if(num[x]!=num[y]) return (void)puts("No");
		c[x]++,d[y]++,c[p]--,d[p]--;
	}
	for(int i=1;i<=tot;i++)
		if(dep[i]==1&&!dfs4(i,0)) return (void)puts("No");
	puts("Yes");
}
signed main()
{
	int T=1;
	while(T--) solve();
}
2024/1/22 07:58
加载中...