自动搬运

查看原文

来自洛谷，原作者为

	llxsmy_forever 似于11.30

搬运于2025-08-24 21:53:25，当前版本为作者最后更新于2023-09-21 20:52:26，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

看到题解大多是用圆方树做的，圆方树是什么，于是蒟蒻来发一篇用点双的题解。

题目描述

给定一张无向连通图，多组询问，每组询问给出点 $X,Y,D$ ，在删除点 $D$ 之后，判断点 $X,Y$ 是否连通。

Solution

对于每组询问，我们分情况讨论。

$\bullet$ 如果 $D$ 点不是割点，那么去掉这个点后这张图显然还是联通的，$X$ 和 $Y$ 当然也是联通的，输出 no。

$\bullet$ 如果点 $X$ 和 $Y$ 处于同一个点双之内，那么不管删除哪一个点， $X$ 和 $Y$ 显然还是联通的，输出 no。

$\bullet$ 最后一种情况，就是 $X$ 和 $Y$ 不在同一个点双之内并且 $D$ 点是割点，这时我们先缩点，此时这张图变成一棵树，设 $tx$ 为 $X$ 所在的点双，$ty$ 为 $Y$ 所在的点双，我们只需判断 $D$ 点是否在 $tx$ 到 $ty$ 的路径上就可以了，在则输出 yes，否则输出 no。

如何判断树上的一个点 $D$ 是否在另两个点 $X$ 和 $Y$ 的路径上呢，我们只需要判断 $dist(X,D)$ 加上 $dist(Y,D)$ 是否等于 $dist(X,Y)$ 就可以了。

Code

#include<bits/stdc++.h>
using namespace std;
const int N=2e4+100,M=1e5+100;
struct edge{int y,pre;}a[M<<1];int alen,last[N];
void ins(int x,int y){alen++;a[alen]={y,last[x]};last[x]=alen;}
int dfn[N],low[N],id,dcc;
int sta[N],top,vis[N],New[N],c[N];
vector<int> q[N];
void tarjan(int x){
	dfn[x]=low[x]=++id;
	sta[++top]=x;
	int cnt=0;
	for(int k=last[x];k;k=a[k].pre){
		int y=a[k].y;
		if(!dfn[y]){
			tarjan(y);
			low[x]=min(low[x],low[y]);
			if(dfn[x]<=low[y]){
				cnt++;
				if(x>1||cnt>1)vis[x]=1;
				int tmp;dcc++;
				do{
					tmp=sta[top--];
					q[dcc].push_back(tmp);
				}while(tmp!=y);
				q[dcc].push_back(x);
			}
		}
		else low[x]=min(low[x],dfn[y]);
	}
}
int dep[N],par[N][21];
void prepare(int x,int fa){
	dep[x]=dep[fa]+1;par[x][0]=fa;
	for(int i=1;i<=19;i++)par[x][i]=par[par[x][i-1]][i-1];
	for(int k=last[x];k;k=a[k].pre){
		int y=a[k].y;
		if(y!=fa)prepare(y,x);
	}
}
int LCA(int x,int y){
	if(dep[x]<dep[y])swap(x,y);
	for(int i=19;i>=0;i--){
		if(dep[par[x][i]]>=dep[y])x=par[x][i];
	}
	if(x==y)return y;
	for(int i=19;i>=0;i--){
		if(par[x][i]!=par[y][i]){
			x=par[x][i],y=par[y][i];
		}
	}
	return par[x][0];
}
int dist(int x,int y,int lca){
	return dep[x]+dep[y]-dep[lca]*2;
}
int main(){
	int n,m;scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int x,y;scanf("%d%d",&x,&y);
		ins(x,y);ins(y,x);
	}
	tarjan(1);
	int sum=dcc;
	for(int i=1;i<=n;i++){
		if(vis[i])New[i]=++sum;
	}
	alen=0;memset(last,0,sizeof(last));
	for(int i=1;i<=dcc;i++){
		for(int j=0;j<q[i].size();j++){
			int x=q[i][j];
			if(vis[x])ins(New[x],i),ins(i,New[x]);
			else c[x]=i;
		}
	}
	prepare(1,0);
	int q;scanf("%d",&q);
	while(q--){
		int x,y,d;scanf("%d%d%d",&x,&y,&d);
		x=vis[x]?New[x]:c[x];
		y=vis[y]?New[y]:c[y];
		if(x==y||!vis[d]){
			puts("no");
			continue;
		}
		d=New[d];
		int lca1=LCA(x,y),lca2=LCA(x,d),lca3=LCA(y,d);
		if(dist(x,y,lca1)==dist(x,d,lca2)+dist(y,d,lca3))puts("yes");
		else puts("no");
	}
	return 0;
}