RT,用圆方树过的,吃了 8 发罚时。
#include<bits/stdc++.h>
using namespace std;
const int N=4e5+5;
int n,m,A,B,C,tot,cnt,dcc[N],t[N],dfn[N],low[N],fa[N],son[N],siz[N],dep[N],top[N];
bool flg[N];
vector<int> G1[N],G2[N];
stack<int> s;
void Tarjan(int u){
low[u]=dfn[u]=++tot;
s.push(u);
for(auto v:G1[u]){
if(!dfn[v]){
Tarjan(v);
low[u]=min(low[u],low[v]);
if(dfn[u]==low[v]){
int tmp;
++cnt;
do{
tmp=s.top();
s.pop();
G2[tmp].push_back(cnt);
G2[cnt].push_back(tmp);
dcc[tmp]=cnt;
} while(tmp!=v);
dcc[u]=cnt;
G2[u].push_back(cnt);
G2[cnt].push_back(u);
}
} else
low[u]=min(low[u],dfn[v]);
}
}
void init(int u,int fa){
low[u]=dfn[u]=++tot;
int num=0;
for(auto v:G1[u]){
if(!dfn[v]){
init(v,u);
++num;
low[u]=min(low[u],low[v]);
if(dfn[u]==low[v]){
if(fa&&low[v]>=dfn[u])
flg[u]=1;
}
} else
low[u]=min(low[u],dfn[v]);
}
if(!fa&&num>=2)
flg[u]=1;
}
void dfs1(int u){
siz[u]=1;
for(auto v:G2[u]){
if(v==fa[u])
continue;
fa[v]=u;
dep[v]=dep[u]+1;
dfs1(v);
siz[u]+=siz[v];
if(siz[v]>siz[son[u]])
son[u]=v;
}
}
void dfs2(int u,int t){
top[u]=t;
if(son[u])
dfs2(son[u],t);
for(auto v:G2[u])
if(v!=son[u]&&v!=fa[u])
dfs2(v,v);
}
inline int LCA(int u,int v){
while(top[u]!=top[v]){
if(dep[top[u]]>dep[top[v]])
swap(u,v);
v=fa[top[v]];
}
if(dep[u]>dep[v])
swap(u,v);
return u;
}
inline int get(int u,int v){
return dep[u]+dep[v]-(dep[LCA(u,v)]<<1);
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m>>A>>B>>C;
for(int i=1,u,v;i<=m;++i){
cin>>u>>v;
G1[u].push_back(v);
G1[v].push_back(u);
}
cnt=n;
init(1,0);
memset(low,0,sizeof(low));
memset(dfn,0,sizeof(dfn));
Tarjan(1);
dfs1(1);
dfs2(1,1);
if(!flg[A]){
A=dcc[A];
for(auto p:G2[A]){
if(p==B){
cout<<"Yes"<<endl;
return 0;
}
}
}
if(!flg[C]){
C=dcc[C];
for(auto p:G2[C]){
if(p==B){
cout<<"Yes"<<endl;
return 0;
}
}
}
if(!flg[B]) B=dcc[B];
if(get(A,C)==get(A,B)+get(B,C))
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
return 0;
}