记录编号	531659	评测结果	AAAWAAAAAT
题目名称	[HZOI 2015]地牢里的背叛	最终得分	80
用户昵称	瑆の時間~無盡輪迴·林蔭	是否通过	未通过
代码语言	C++	运行时间	1.560 s
提交时间	2019-05-18 16:58:06	内存使用	22.42 MiB

#include<iostream> 
#include<cstdio>
#include<cstring>
using namespace std;
int dfn[200001];
int low[200001];
bool bridge[400001];
int head[200001];
int e[400001];
int next[400001];
int E_DCC[200001];
int n,m,q,cnt=1,a1,a2,num=0,dcc=0;
int hc[200001],vc[400001],nc[400001],tc;
bool E_DCCPD[200001];
int fa[200001];
bool pds=0;
void hb(int x,int y)
{
	fa[y]=x;
}
int find(int x)
{
	if(x==fa[x])
	{
		return x;
	}
	return fa[x]=find(fa[x]);
}
void ADD_C(int x,int y)
{
	vc[++tc]=y;
	nc[tc]=hc[x];//lydrainbowcat的流派前向星写法，切记 
	hc[x]=tc;
}
void ADD(int u,int v)
{
	e[++cnt]=v;
	next[cnt]=head[u];//lydrainbowcat的流派前向星写法，切记 
	head[u]=cnt;
}
void TARJAN(int x,int in_edge)
{
	dfn[x]=low[x]=++num;
	for(register int i=head[x];i;i=next[i])
	{
		int y=e[i];
		if(!dfn[y])
		{
			TARJAN(y,i);
			low[x]=min(low[y],low[x]);
			if(low[y]>dfn[x])
			{
				bridge[i]=bridge[i^1]=true;
			}
		}
		else
		{
			if(i!=(in_edge^1))//一定要加（in_edge^1)的括号 
			{
				low[x]=min(low[x],dfn[y]);
			}
		}
	}
}
void findE_DCC(int x)
{
	E_DCC[x]=dcc;
	for(register int i=head[x];i;i=next[i])
	{
		if(E_DCC[e[i]]||bridge[i])
		{
			continue;
		}
		findE_DCC(e[i]);
	}
}
void FINDDFS(int x,int fa)
{
	//cout<<x<<endl;
	E_DCCPD[x]=1;
	for(register int i=hc[x];i;i=nc[i])
	{
		if(pds==1)
			return;
		int y=vc[i];
		//cout<<y<<' ';
		if(y==fa||E_DCCPD[y]==1)
		{
			continue;
		}
		if(y==a2)
		{
			pds=1;
			return;
		}
		FINDDFS(y,x);
	}
}
int LINYIN()
{
	freopen("MM.in","r",stdin);
	freopen("MM.out","w",stdout);
	scanf("%d%d%d",&n,&m,&q);
	for(register int i=1;i<=m;i++)
	{
		scanf("%d%d",&a1,&a2);
		ADD(a1,a2);
		ADD(a2,a1);
	}
	for(register int i=1;i<=n;i++)
	{
		if(!dfn[i])
		{
			TARJAN(i,0);
		}
	}
	for(register int i=1;i<=n;i++)
	{
		if(!E_DCC[i])
		{
			dcc++;
			findE_DCC(i);
		}
	}
	/*for(int i=2;i<cnt;i+=2)
	{
		if(bridge[i])
		{
			cout<<e[i^1]<<' '<<e[i]<<endl;
		}
	}
	for(int i=1;i<=n;i++)
	{
		cout<<E_DCC[i]<<' ';
	}*/
	tc=1;
	for(int i=1;i<=n;i++)
	{
		fa[i]=i;
	}
	for(register int i=2;i<=cnt;i++)
	{
		int x=e[i^1],y=e[i];
		int f1=find(x);
		int f2=find(y);
		if(E_DCC[x]==E_DCC[y]||f1==f2)
		{
			continue;
		}
		ADD_C(E_DCC[x],E_DCC[y]); 
		ADD_C(E_DCC[y],E_DCC[x]);
		hb(f1,f2);
	}
	for(register int i=1;i<=q;i++)
	{
		scanf("%d%d",&a1,&a2);
		memset(E_DCCPD,0,sizeof(E_DCCPD));
		a1=E_DCC[a1];
		a2=E_DCC[a2];
		pds=0;
		FINDDFS(a1,0);
		if(pds==0&&a1!=a2)
		{
			cout<<"No";
			return 0;
		} 
	}
	cout<<"Yes";
	return 0;
}
int sde=LINYIN();
int main()
{
	;
}