牛客多校第三场 F 题题解

F 题意：有一个 $nn$ 个点 $mm$ 条边的无向图 $GG$，$qq$ 次询问，每次询问给定 $x_i,y_{i}x\_i,y\_i$，表示一个长度为 $nn$ 的排列的第一项和最后一项，问是否能找到一个长度为 $nn$ 且首尾项为 $x_{i}x\_i$ 和 $y_{i}y\_i$ 的排列，使得 $\mathrm{\forall }i\in [1,n-1]\backslash forall\; i\; \backslash in\; [1,n-1]$，排列的前 $ii$ 项构成的子图和后 $n-in-i$ 项均联通。$n,q\le 1\times 10^{5}n,q\; \backslash leq\; 1\backslash times\; 10^5$，$m\le 2\times 10^{5}m\; \backslash leq\; 2\backslash times\; 10^5$。

解法：考虑以割点进行缩图。

首先考虑几种特殊情况：

1. 原图仅两个点，必然成立。
2. 原图无割点，即全图为点双连通，则必然成立。
3. 原图不连通，必然不成立。

对于一个朴素的连通且具有割点的图，缩完点后的图 $G^{\mathrm{\prime }}G\text{'}$ 必然为一条链——若 $G^{\mathrm{\prime }}G\text{'}$ 上存在一度数大于等于 $33$ 的节点，记为 $uu$，从 $uu$ 割出的某一连通分量出发，必然在随着排列的前 $ii$ 项数量从小到大的扩张过程中扩张到 $uu$，且后续还要继续扩张。而一旦扩张到 $uu$，后 $n-in-i$ 项不连通。

进一步的，考虑 $x_{i}x\_i$ 和 $y_{i}y\_i$ 在 $G^{\mathrm{\prime }}G\text{'}$ 上的位置——若不是分属链的两端点，必然不成立——假设 $x_{i}x\_i$ 不在端点，则 $y_{i}y\_i$ 必然会因为 $x_{i}x\_i$ 的阻断导致不能和两个链端点同时连通，对于 $i=2i=2$ 的情况就失败了。

代码来源于队友。

#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define IL inline
#define LL long long
#define pb push_back
using namespace std;
const int N=2e5+3;
struct hh{
	int to,nxt;
}e[N<<1];
int n,m,q,num,col,tp,sta[N],fir[N],dfn[N],low[N],val[N];
vector<int>e1[N],e2[N];
IL int in(){
    char c;int f=1;
    while((c=getchar())<'0'||c>'9')
      if(c=='-') f=-1;
    int x=c-'0';
    while((c=getchar())>='0'&&c<='9')
      x=x*10+c-'0';
    return x*f;
}
IL void add(int x,int y){e[++num]=(hh){y,fir[x]},fir[x]=num;}
void tarjan(int u){
	dfn[u]=low[u]=++num,sta[++tp]=u;
	for(int i=fir[u],v;v=e[i].to;i=e[i].nxt)
	  if(!dfn[v]){
	  	tarjan(v),low[u]=min(low[u],low[v]);
	  	if(dfn[u]<=low[v]){
	  		++col;
	  		while(sta[tp+1]!=v)
	  		  e1[sta[tp]].pb(col),
	  		  e2[col].pb(sta[tp--]);
	  		e1[u].pb(col),e2[col].pb(u);
	  	}
	  }
	  else low[u]=min(low[u],dfn[v]);
}
IL void print(int op){for(int i=1;i<=q;++i) puts(op?"YES":"NO");exit(0);}
int main()
{
	int x,y,z;
	n=in(),m=in();
	for(int i=1;i<=m;++i)
	  x=in(),y=in(),add(x,y),add(y,x);
	q=in(),num=0,tarjan(1),num=0;
	if(n==2) print(1);
	for(int i=1;i<=n;++i)
	  if(!dfn[i]||e1[i].size()>2) print(0);
	if(col==1) print(1);
	for(int i=1;i<=col;++i){
		int deg=0;
		for(int j=0;j<e2[i].size();++j)
		  deg+=e1[e2[i][j]].size()-1;
		if(deg>2) print(0);
		if(deg==1){
			++num;
			for(int j=0;j<e2[i].size();++j)
			  if(e1[e2[i][j]].size()==1) val[e2[i][j]]=num;
		}
	}
	while(q--) puts(val[in()]+val[in()]^3?"NO":"YES");
  return 0;
}