您的位置: 首页  >  IT文章  >  题解 CF555E 【Case of Computer Network】

题解 CF555E 【Case of Computer Network】

分类: IT文章 • 2023-11-08 19:44:25

思路：

(quad)先缩点(找边双)，注意一条边只能走一次，缩完点后图就变成了一棵树(或森林，可能有不连通的情况，注意要额外记录是否在一个连通块中)。

(quad)对于每一个询问 (x) -> (y) ，若在一个强连通分量中(边双)不考虑，直接跳过，若不在一个连通块(树)中，直接输出 ("No") ，否则对 (x) 到 (y) 的路径修改，从x向上跳是修改 (up) 数组，从 (y) 向上跳时修改 (down) 数组，在同一条链上时判断深度，注意方向是从 (x) 到 (y) 的方向，修改的是边权最后一次跳要 (+1) ，最后判断每一条边是否只有向上跳或向下跳(边的方向)，若两个都有就输出 ("No") ，有矛盾，最后输出 ("Yes") 即可。

前置知识：(Tarjan) 缩点 (+) 树链剖分 (+) 线段树

#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<algorithm>
#include<map>
#include<queue>
#include<stack>
#include<cstring>
using namespace std;
#define re register int
#define int long long
#define LL long long
#define il inline
#define next nee
#define inf 1e18
il int read()
{
  int x=0,f=1;char ch=getchar();
  while(!isdigit(ch)&&ch!='-')ch=getchar();
  if(ch=='-')f=-1,ch=getchar();
  while(isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
  return x*f;
}
il void print(int x)
{
  if(x<0)putchar('-'),x=-x;
  if(x/10)print(x/10);
  putchar(x%10+'0');
}
const int N=2e5+5;
int n,m,q1,next[N<<1],go[N<<1],u[N],v[N],head[N],tot,dfn[N],top[N];
int size[N],cnt,c[N],dep[N],low[N],d[N],father[N],son[N],seg[N];
bool b[N<<1],flag,up[N<<2],down[N<<2];
stack<int>q;
il void Add(int x,int y)
{
  next[++tot]=head[x];
  head[x]=tot;
  go[tot]=y;
}
il void Tarjan(int x,int fa)//缩点
{
  dfn[x]=low[x]=++cnt;d[x]=fa;
  q.push(x);
  for(re i=head[x];i;i=next[i])
    {
      if(b[i]||b[i^1])continue;b[i]=1;
      int y=go[i];
      if(!dfn[y])Tarjan(y,fa),low[x]=min(low[x],low[y]);
      else if(!c[y])low[x]=min(low[x],dfn[y]);
    }
  if(dfn[x]==low[x])
    {
      c[x]=++c[0];
      while(q.top()!=x)
	{
	  c[q.top()]=c[0];
	  q.pop();
	}
      q.pop();
    }
}
il void dfs1(int x,int fa)
{
  dep[x]=dep[fa]+1;father[x]=fa;size[x]=1;
  for(re i=head[x];i;i=next[i])
    {
      int y=go[i];
      if(y==fa)continue;
      dfs1(y,x);
      size[x]+=size[y];
      if(size[y]>size[son[x]])son[x]=y;
    }
}
il void dfs2(int x,int topf)
{
  top[x]=topf;seg[x]=++seg[0];
  if(!son[x])return;
  dfs2(son[x],topf);
  for(re i=head[x];i;i=next[i])
    {
      int y=go[i];
      if(top[y])continue;
      dfs2(y,y);
    }
}
il void pushdown(int k,int l,int r,int mid)
{
  if(down[k])down[k<<1]=down[k<<1|1]=1;
  if(up[k])up[k<<1]=up[k<<1|1]=1;
}
il void change1(int k,int l,int r,int x,int y,int z)
{
  if(x<=l&&y>=r){if(z==1)down[k]=1;else up[k]=1;return;}
  int mid=l+r>>1;
  if(down[k]||up[k])pushdown(k,l,r,mid);
  if(x<=mid)change1(k<<1,l,mid,x,y,z);
  if(y>mid)change1(k<<1|1,mid+1,r,x,y,z);
}
il void change(int x,int y)
{
  int fx=top[x],fy=top[y];
  while(fx!=fy)
    {
      if(dep[fx]>dep[fy]){
	change1(1,1,c[0],seg[fx],seg[x],2);
	x=father[fx];fx=top[x];
      }
      else {
	change1(1,1,c[0],seg[fy],seg[y],1);
	y=father[fy];fy=top[y];
      }
    }
  if(seg[y]+1<=seg[x])change1(1,1,c[0],seg[y]+1,seg[x],2);
  else if(seg[x]+1<=seg[y])change1(1,1,c[0],seg[x]+1,seg[y],1);
}
il bool check(int k,int l,int r)//最后检查每一条边
{
  if(l==r){if(down[k]&&up[k])return 0;else return 1;}
  int mid=l+r>>1;
  if(down[k]||up[k])pushdown(k,l,r,mid);
  return min(check(k<<1,l,mid),check(k<<1|1,mid+1,r));
}
signed main()
{
  n=read();m=read();q1=read();tot=1;
  for(re i=1;i<=m;i++)
    {
      re x=read(),y=read();
      u[i]=x;v[i]=y;
      Add(x,y);Add(y,x);
    }
  for(re i=1;i<=n;i++)
  if(!dfn[i])Tarjan(i,i);//缩点
  memset(next,0,sizeof(next));
  memset(head,0,sizeof(head));
  memset(go,0,sizeof(go));
  tot=0;
  for(re i=1;i<=m;i++)
    {
      int x=c[u[i]],y=c[v[i]];
      if(x!=y)Add(x,y),Add(y,x);
    }
  for(re i=1;i<=n;i++)//树剖预处理
    if(!dep[i])dfs1(i,0),dfs2(i,i);//可能有多棵树
  for(re i=1;i<=q1;i++)
    {
      int u1=read(),v1=read();
      if(d[u1]!=d[v1]){puts("No");return 0;}//是否在一个连通块中
      if(c[u1]!=c[v1])change(c[u1],c[v1]);//若不在一个强连通分量，就修改
      }
  if(check(1,1,c[0]))puts("Yes");
  else puts("No");
  return 0;
}

相关推荐