“蔚来杯“2022牛客暑期多校训练营3 F.Fief (点双联通分量）

题意

给定一个无向图，每次询问两点x, y，求是否存在一个n的排列，使得第一个元素为x，最后一个元素为y，且排列的任意一个前缀、任意一个后缀都连通。

我们对其进行点双缩点如果图不连通 或者某个点属于 三个连通分量 或者某个连通分量的里的点链接了三个连通分量 手玩一下显然不可以 我们只有在缩点后在链两端的才可以

#include <bits/stdc++.h>
using namespace
std;
#define
int long long
//typedef long long ll;
typedef pair<int,int> pii;
#define x first
#define y second
#define pb
push_back
#define inf 1e18
#define IOS
std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define
fer(i,a,b)
for(int i=a;i<=b;i++)
#define
der(i,a,b)
for(int i=a;i>=b;i--)
const int maxn=1e5+10;
const int mod=1e9+7;
int qmi(int a,int b) {
int res=1;
while(b) {
if(b&1) res=res*a%mod;
a=a*a%mod;
b>>=1;
}
return res;
}
const int N=2e5+10;
int dr[4][2]= {{-1,0},{1,0},{0,-1},{0,1}};
int n,k;
vector<int>g[N];
vector<int>cc[N];
vector<int>bel[N];
int p[N];
int m;
int idx,cnt,low[N],dfn[N],cut[N];
int sum;
stack<int>s;
void dfs(int u,int fa) {
low[u]=dfn[u]=++idx;
s.push(u);
int ch=0;
for(auto v:g[u]) {
if(!dfn[v]) {
ch++;
dfs(v,u);
low[u]=min(low[u],low[v]);
if(low[v]>=dfn[u]) {
++cnt;
bel[u].push_back(cnt);
cc[cnt].push_back(u);
while(1) {
int w=s.top();
s.pop();
bel[w].push_back(cnt);
cc[cnt].push_back(w);
if(w==v)break;
}
}
} else if(v!=fa)low[u]=min(low[u],dfn[v]);
}
if(ch<=1&&u==1)cut[u]=0;
}
void
printyes() {
while(k--)puts("YES");
}
void printno() {
while(k--)puts("NO");
}
void solve() {
cin>>n>>m;
fer(i,1,m) {
int a,b;
cin>>a>>b;
g[a].push_back(b);
g[b].push_back(a);
}
cin>>k;
if(n<=2) {
printyes();
return ;
}
dfs(1,0);
fer(i,1,n) {
if(!dfn[i]||bel[i].size()>2) {
printno();
return
;
}
}
if(cnt==1) {
printyes();
return ;
}
int tt=0;
fer(i,1,cnt) {
sum=0;
for(auto v:cc[i])sum+=bel[v].size()-1;
if(sum>2) {
printno();
return ;
}
if(sum!=1)continue;
tt++;
for(auto v:cc[i]) {
if(bel[v].size()==1)p[v]=tt;
}
}
while(k--) {
int l,r;
cin>>l>>r;
if(p[l]+p[r]==3)puts("YES");
else puts("NO");
}
}
signed main() {
IOS;
int _=1;
//cin>>_;
while(_--) solve();
return 0;
}

最后

以上就是合适丝袜为你收集整理的“蔚来杯“2022牛客暑期多校训练营3 F.Fief (点双联通分量）的全部内容，希望文章能够帮你解决“蔚来杯“2022牛客暑期多校训练营3 F.Fief (点双联通分量）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。