分析

一个连通块内的肯定不影响

于是我们先缩点

之后对于每个路径

向上向下分别开一个差分数组

如果两个数组同时有值则不合法

代码

#include<bits/stdc++.h>
using namespace std;
int n,m,q,bl[],s[],t[],dfn[],low[],is[];
int cnt,tot,sum,head[],nxt[],to[],ano[];
int d1[],d2[],dep[],pr[][];
int f[],vis[],vis2[];
vector<int>v[];
stack<int>a;
inline int sf(int x){return f[x]==x?x:f[x]=sf(f[x]);}
inline void add(int x,int y){
nxt[++tot]=head[x],head[x]=tot,to[tot]=y,ano[tot]=tot+;
nxt[++tot]=head[y],head[y]=tot,to[tot]=x,ano[tot]=tot-;
}
inline void tarjan(int x,int id){
dfn[x]=low[x]=++cnt;
a.push(x),is[x]=;
for(int i=head[x];i;i=nxt[i])
if(i!=ano[id]){
if(!dfn[to[i]]){
tarjan(to[i],i);
low[x]=min(low[x],low[to[i]]);
}else if(is[to[i]]){
low[x]=min(low[x],dfn[to[i]]);
}
}
if(low[x]==dfn[x]){
sum++;
while(){
int u=a.top();
a.pop(),is[u]=;
bl[u]=sum;
if(u==x)break;
}
}
}
inline void dfs(int x,int fa){
vis2[x]=;
pr[x][]=fa;
dep[x]=dep[fa]+;
for(int i=;i<v[x].size();i++)
if(v[x][i]!=fa)dfs(v[x][i],x);
}
inline int lca(int x,int y){
if(dep[x]<dep[y])swap(x,y);
int i,j,k,len=dep[x]-dep[y];
for(i=;i<=;i++)
if((<<i)&len)x=pr[x][i];
if(x==y)return x;
for(i=;i>=;i--)
if(pr[x][i]!=pr[y][i])
x=pr[x][i],y=pr[y][i];
return pr[x][];
}
inline void dfs2(int x,int fa){
vis[x]=;
for(int i=;i<v[x].size();i++)
if(v[x][i]!=fa)dfs2(v[x][i],x),d1[x]+=d1[v[x][i]],d2[x]+=d2[v[x][i]];
if(d1[x]>&&d2[x]>){
puts("No");
exit();
}
}
int main(){
int i,j,k;
scanf("%d%d%d",&n,&m,&q);
for(i=;i<=m;i++){
int x,y;
scanf("%d%d",&x,&y);
add(x,y);
if(sf(x)!=sf(y))f[sf(x)]=sf(y);
}
for(i=;i<=q;i++)scanf("%d%d",&s[i],&t[i]);
for(i=;i<=q;i++)if(sf(s[i])!=sf(t[i])){puts("No");return ;}
for(i=;i<=n;i++)if(!dfn[i])tarjan(i,);
for(i=;i<=n;i++)
for(j=head[i];j;j=nxt[j])
if(bl[i]!=bl[to[j]])v[bl[i]].push_back(bl[to[j]]);
for(i=;i<=sum;i++)if(!vis2[i])dfs(i,);
for(i=;i<=;i++)
for(j=;j<=sum;j++)
pr[j][i]=pr[pr[j][i-]][i-];
for(i=;i<=q;i++){
if(bl[s[i]]==bl[t[i]])continue;
int x=bl[s[i]],y=bl[t[i]],z=lca(x,y);
d1[x]++,d1[z]--;
d2[y]++,d2[z]--;
}
for(i=;i<=sum;i++)if(!vis[i])dfs2(i,);
puts("Yes");
return ;
}

最新文章

  1. Vue - class与style绑定
  2. android-sdk 开发连接不上
  3. C#学习网站记录
  4. 12个css高级技巧.html
  5. 【UVA 1586】Ancient Cipher
  6. MyEclipse8.5集成Tomcat7
  7. Android实例-Delphi开发蓝牙官方实例解析(XE10+小米2+小米5)
  8. java之内部类与匿名内部类
  9. 多线程与网络之SDWebImage和NSCache
  10. 非常实用的JQuery的选项卡切换源码
  11. (6/18)重学Standford_iOS7开发_控制器多态性、导航控制器、选项卡栏控制器_课程笔记
  12. 解决 asp.net 伪静态 IIS设置后 直正HTML无法显示的问题
  13. ssh环境搭建并实现登录功能
  14. OpenCV 开发环境环境搭建(win10+vs2015+opencv 3.0)
  15. 数字雨Shopex 4.8.5 SQL Injection Exp
  16. Java的设计模式----strategy(策略模式)
  17. phpStudy2016 配置多个域名期间遇到的问题
  18. javascript中快速求数组的全部元素的相加之和
  19. js实现图片(高度不确定)懒加载
  20. kcp-go源码解析

热门文章

  1. oracle常用函数(2)
  2. js 元素offset,client , scroll 三大系列总结
  3. Python3 A*寻路算法实现
  4. Jmeter线程组间传递参数
  5. Linux抓包与扫描工具
  6. ArrayList与LinkedList的区别
  7. js - 基础 之 预编译总结
  8. Java基本的程序结构设计 控制流程
  9. 一个web应用的诞生(6)
  10. vue-项目模块化中this 指向问题