题目大意
给定一个n个点，m条边的无向图。有q条有向路线分别从si到达ti。
现在你要给无向图的每条边分配一个方向。问是否存在一种分配答案使得所有路线都能够被满足。
1≤n,m,q≤2×105
题目分析
首先我们考虑对这个图做边双连通分量，可以证明，边双内一定存在一个不经过同样的边的环把每个点至少经过一次。
然后我们把边双缩起来，问题就变成给你一个树（其实严格来说可能是森林），然后要你分配方向来满足一些路线。
我们可以单独考虑每一条边，看看经过它的路线是不是两个方向都有。这个可以使用打
标记然后求子树和来解决。
如果求LCA用的是Tarjan的话就可以O(n)，否则就是O(nlogn)的。
注意不连通的情况哦。
代码实现
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cctype>
using namespace std;
int read()
{
int x=0,f=1;
char ch=getchar();
while (!isdigit(ch)) f=ch=='-'?-1:f,ch=getchar();
while (isdigit(ch)) x=x*10+ch-'0',ch=getchar();
return x*f;
}
const int N=200005;
const int M=200005;
const int E=M<<1;
const int LGN=18;
int DFN[N],low[N],last[N],high[N],bel[N],fa[N],conid[N],stack[N],LOG[N],size[N],sum[N][2];
int tov[E],nxt[E],rev[E];
int anc[N][LGN];
int n,m,q,tot,idx,cnt,btot,top;
bool res;
void insert(int x,int y,int r=0){tov[++tot]=y,rev[tot]=tot+r,nxt[tot]=last[x],last[x]=tot;}
void tarjan(int x,int e)
{
DFN[x]=low[x]=++idx,conid[x]=btot,stack[++top]=x;
for (int i=last[x],y;i;i=nxt[i])
if (i!=e)
if (!DFN[y=tov[i]]) tarjan(y,rev[i]),low[x]=min(low[x],low[y]);
else low[x]=min(low[x],DFN[y]);
if (DFN[x]==low[x])
{
int y;
fa[++cnt]=tov[e];
do
{
y=stack[top--],bel[y]=cnt;
}while (x!=y);
}
}
void dfs(int x)
{
DFN[x]=++idx,size[x]=1;
for (int i=last[x],y;i;i=nxt[i]) high[y=tov[i]]=high[x]+1,dfs(y),size[x]+=size[y];
}
void
PRe()
{
for (int i=1;i<=cnt;++i) if (fa[i]) fa[i]=bel[fa[i]];
for (;tot;nxt[tot]=rev[tot]=tov[tot]=0,--tot);
for (int i=1;i<=cnt;++i) last[i]=DFN[i]=0;
idx=0;
for (int i=1;i<=cnt;++i) if (fa[i]) insert(fa[i],i),anc[i][0]=fa[i];
LOG[1]=0;
for (int i=2;i<=cnt;++i) LOG[i]=LOG[i-1]+(1<<LOG[i-1]+1==i);
for (int j=1;j<=LOG[cnt];++j)
for (int i=1;i<=cnt;++i)
anc[i][j]=anc[anc[i][j-1]][j-1];
for (int i=1;i<=cnt;++i) if (!fa[i]) high[i]=1,dfs(i);
}
int adjust(int x,int h)
{
for (int i=LOG[high[x]];i>=0;--i)
if (high[anc[x][i]]>=h) x=anc[x][i];
return x;
}
int lca(int x,int y)
{
if (high[x]>high[y]) swap(x,y);
y=adjust(y,high[x]);
if (x==y) return x;
for (int i=LOG[high[x]];i>=0;--i)
if (anc[x][i]!=anc[y][i]) x=anc[x][i],y=anc[y][i];
return fa[x];
}
bool judge(int x){return sum[DFN[x]+size[x]-1][0]-sum[DFN[x]-1][0]&&sum[DFN[x]+size[x]-1][1]-sum[DFN[x]-1][1];}
int main()
{
freopen("network.in","r",stdin),freopen("network.out","w",stdout);
n=read(),m=read(),q=read();
for (int i=1,x,y;i<=m;++i) x=read(),y=read(),insert(x,y,1),insert(y,x,-1);
for (int i=1;i<=n;++i) if (!DFN[i]) ++btot,tarjan(i,0);
pre();
res=1;
for (int i=1,x,y,z;i<=q;++i)
{
x=read(),y=read();
if (conid[x]!=conid[y])
{
res=0;
break;
}
x=bel[x],y=bel[y],z=lca(x,y);
++sum[DFN[x]][0],--sum[DFN[z]][0],++sum[DFN[y]][1],--sum[DFN[z]][1];
}
for (int i=1;i<=cnt;++i) sum[i][0]+=sum[i-1][0],sum[i][1]+=sum[i-1][1];
for (int i=1;i<=cnt&&res;++i) if (judge(i)) res=0;
printf(res?"Yes\n":"No\n");
fclose(stdin),fclose(stdout);
return 0;
}
