题目大意
给你一个
n
n
n 个点和
m
m
m 条边的无向图,并有
Q
Q
Q 个询问,每次询问有两种形式:
1.1 X Y P Q , 表示在删掉
P
P
P 和
Q
Q
Q 之间的连边后
X
X
X 和
Y
Y
Y 是否相互可达(保证
P
P
P 和
Q
Q
Q 有边相连)
2.2 X Y P,表示在删掉点
P
P
P 后
X
X
X 和
Y
Y
Y 是否相互可达。
若可达,输出
y
e
s
yes
yes ,否则输出
n
o
no
no。
数据范围
n ≤ 1 0 5 , m ≤ 5 ∗ 1 0 5 , Q ≤ 5 ∗ 1 0 5 n \le 10^5 ,m \le 5*10^5 ,Q \le 5*10^5 n≤105,m≤5∗105,Q≤5∗105 。
思路
看到删掉点或边是否可达,我们可以想到割点和桥,倘若删掉的点或边不为割点或桥,那就证明互相可达(前提是
X
X
X 和
Y
Y
Y 互相可达)。
对于求割点和桥,我们可以用
T
a
r
j
a
n
Tarjan
Tarjan 预处理出来每一个点的
d
f
s
dfs
dfs 序
d
f
n
i
dfn_{i}
dfni 以及每个点可以到达的最小的节点(双亲除外)的最小深度优先数(即
d
f
n
dfn
dfn)
l
o
w
i
low_{i}
lowi ,然后我们就可以用所处理出来的
d
f
n
dfn
dfn 和
l
o
w
low
low 搞事情 解题啦!
删边操作:
1.若
X
X
X 和
Y
Y
Y 不在一个连通图里: 输出
n
o
no
no 。
2.若边
(
P
,
Q
)
(P,Q)
(P,Q) 不为桥:输出
y
e
s
yes
yes 。
3.若点
X
X
X 和
Y
Y
Y 均在
P
(
Q
)
P(Q)
P(Q) 的子树内,如图:
肯定有一条路径不经过边
(
P
,
Q
)
(P,Q)
(P,Q) 的,输出
y
e
s
yes
yes 。
4.若点
X
X
X 和点
Y
Y
Y 均不在点
P
(
Q
)
P(Q)
P(Q) 内(和上图一样),输出
y
e
s
yes
yes 。
5.剩余情况:输出
n
o
no
no。
删点操作
同样要先判断
X
X
X 和
Y
Y
Y 是否在同一连通图内部。
若点
P
P
P 不为割点,输出
y
e
s
yes
yes 即可。
然后判断
X
X
X 和
Y
Y
Y 在
P
P
P 的哪颗子树,如图:
设点
y
a
ya
ya 为点
X
X
X 在点
P
P
P 的儿子
y
a
ya
ya 的子树内,点
y
b
yb
yb 为点
Y
Y
Y 在点
P
P
P 的儿子
y
b
yb
yb 的子树内。
1.若点
X
X
X 和点
Y
Y
Y均不在
P
P
P 的子树内(如
x
1
,
y
1
x1,y1
x1,y1),输出
y
e
s
yes
yes 。
2.若点
X
X
X 和点
Y
Y
Y 均在
P
P
P 的子树内(如
x
2
,
y
2
x2,y2
x2,y2):
如果
l
o
w
y
a
>
d
f
n
p
low_{ya} > dfn_{p}
lowya>dfnp 且
l
o
w
y
b
>
d
f
n
p
low_{yb}>dfn_{p}
lowyb>dfnp (即点
X
X
X 和点
Y
Y
Y均有一条路径可以连向
P
P
P的祖先),输出
y
e
s
yes
yes ,否则输出
n
o
no
no 。
3.若点
X
X
X 和点
Y
Y
Y 其一在
P
P
P 的子树内(如
x
3
,
y
3
x3,y3
x3,y3),设点
Y
Y
Y 在点
P
P
P 的子树内:
如果
l
o
w
y
b
>
d
f
n
p
low_{yb}>dfn_{p}
lowyb>dfnp (即
Y
Y
Y 有一条路径可以到达
P
P
P 的祖先),输出
y
e
s
yes
yes ,否则输出
n
o
no
no 。
求是否在子树内可以处理出每个点的子树大小
s
i
z
e
size
size 。
求为那个儿子内可以用倍增在线求,也可以用栈离线求。
分类讨论较多,但实质不难,细心点就可以通过了。
AC代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
struct node{
int head,to,nxt;
}edge[1000200];
struct pu{
int dfn,dep,low,wz,sz,col;
}tree[1000200];
int n,m,a,b,opt,Q,cnt,sta[1000200],top,tot,f[200200][22],sc;
bool vis[1000200],in_stack[1000200];
bool ge[1000200],isbridge[1000200];
void xx(int u,int v)
{
edge[cnt].to=v;
edge[cnt].nxt=edge[u].head;
edge[u].head=cnt;
cnt++;
}
void tarjan(int x,int father,int col)
{
vis[x]=1;
tot++,top++;
sta[top]=tot;
in_stack[x]=1;
tree[x].low=tree[x].dfn=tot;
tree[x].col=col,tree[x].dep=tree[father].dep+1;
tree[x].sz=1;
// printf("!!!%d %d\n",x,tree[x].low);
for(int i=1;(1<<i)<=tree[x].dep;i++)
f[x][i]=f[f[x][i-1]][i-1];
for(int i=edge[x].head;i!=-1;i=edge[i].nxt)
{
int y=edge[i].to;
if(y==father)
continue;
// printf("!!!%d %d\n",x,y);
if(!vis[y])
{
f[y][0]=x;
tarjan(y,x,col);
tree[x].sz+=tree[y].sz;
tree[x].low=min(tree[x].low,tree[y].low);
}
else if(in_stack[y])
tree[x].low=min(tree[x].low,tree[y].dfn);
}
}
int lca(int u,int v)
{
if(tree[u].dep<tree[v].dep)
swap(u,v);
for(int i=20;i>=0;i--)
{
if(tree[f[u][i]].dep>=tree[v].dep)
u=f[u][i];
if(u==v)
return u;
}
for(int i=20;i>=0;i--)
{
if(f[u][i]!=f[v][i])
u=f[u][i],v=f[v][i];
}
return f[u][0];
}
int find_son(int x,int y)
{
for(int i=20;i>=0;i--)
if(tree[f[x][i]].dep>tree[y].dep)
x=f[x][i];
return x;
}
bool in(int x,int y)
{
if(tree[y].dfn<=tree[x].dfn&&tree[y].dfn+tree[y].sz-1>=tree[x].dfn)
return 1;
return 0;
}
int main()
{
// freopen("check.in","r",stdin);
// freopen("a.out","w",stdout);
memset(edge,-1,sizeof(edge));
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++)
scanf("%d %d",&a,&b),xx(a,b),xx(b,a);
for(int i=1;i<=n;i++)
if(!vis[i])
tarjan(i,0,i);
// printf("!\n");
// int qwq=0;
scanf("%d",&Q);
while(Q--)
{
scanf("%d",&opt);
// qwq++;
// printf("%d ",qwq);
if(opt==1)
{
int x,y,p,q;
scanf("%d %d %d %d",&x,&y,&p,&q);
int LCA=lca(x,y);
if(tree[x].dfn<tree[y].dfn)
swap(x,y);
if(tree[p].dfn<tree[q].dfn)
swap(p,q);
if(tree[x].col!=tree[y].col)
{
printf("no\n");
continue;
}
if(tree[p].low<=tree[q].dfn)
{
printf("yes\n");
continue;
}
if((in(x,p)&&in(y,p))||(!in(x,p)&&!in(y,p)))
{
printf("yes\n");
continue;
}
printf("no\n");
continue;
}
else
{
int x,y,p;
scanf("%d %d %d",&x,&y,&p);
int LCA=lca(x,y);
if(tree[x].col!=tree[y].col)
{
printf("no\n");
continue;
}
if(x==p||y==p)
{
printf("no\n");
continue;
}
if(!in(x,p)&&!in(y,p))
{
printf("yes\n");
continue;
}
if(in(y,p))
swap(x,y);
if(!in(y,p))
{
int ya=find_son(x,p);
if(tree[ya].low<tree[p].dfn)
printf("yes\n");
else
printf("no\n");
continue;
}
else
{
int ya=find_son(x,p),yb=find_son(y,p);
if(tree[ya].low<tree[p].dfn&&tree[yb].low<tree[p].dfn||ya==yb)
printf("yes\n");
else
printf("no\n");
continue;
}
}
}
}