Problem Statement
You are given a simple connected undirected graph $G$ with $N$ vertices and $M$ edges.
The vertices and edges of $G$ are numbered as vertex $1$, vertex $2$, $\ldots$, vertex $N$, and edge $1$, edge $2$, $\ldots$, edge $M$, respectively, and edge $i$ $(1\leq i\leq M)$ connects vertices $U_i$ and $V_i$.
You are also given distinct vertices $A,B,C$ on $G$. Determine if there is a simple path connecting vertices $A$ and $C$ via vertex $B$.
What is a simple connected undirected graph?
A graph $G$ is said to be a simple connected undirected graph when $G$ is an undirected graph that is simple and connected.A graph $G$ is said to be an undirected graph when the edges of $G$ have no direction.
A graph $G$ is simple when $G$ does not contain self-loops or multi-edges.
A graph $G$ is connected when one can travel between all vertices of $G$ via edges.
Constraints
- $3 \leq N \leq 2\times 10^5$
- $N-1\leq M\leq\min\left(\frac{N(N-1)}{2},2\times 10^5\right)$
- $1\leq A,B,C\leq N$
- $A$, $B$, and $C$ are all distinct.
- $1\leq U_i<V_i\leq N$
- The pairs $(U_i,V_i)$ are all distinct.
- All input values are integers.
点不能重复，考虑圆方树。
如果 \(A,B,C\) 在一个点双内，那么一定没问题。因为删掉B 这个点一定还有路径可以到 \(C\)
那么在圆方树上的体现就是 A,B,C 连着同一个方点。
以此类推，如果 \(A,C\) 在圆方树上的路径通过了一个 B 所连的方点，那么就可以，否则割点不能重复走，所以不行。
#include<bits/stdc++.h>
using namespace std;
const int N=4e5+5;
int n,m,a,b,c,vs[N],st[N],tp,idx,dfn[N],low[N];
struct graph{
int hd[N],e_num;
struct edge{
int v,nxt;
}e[N<<1];
void add_edge(int u,int v)
{
e[++e_num]=(edge){v,hd[u]};
hd[u]=e_num;
e[++e_num]=(edge){u,hd[v]};
hd[v]=e_num;
}
}g,h;
int read()
{
int s=0;
char ch=getchar();
while(ch<'0'||ch>'9')
ch=getchar();
while(ch>='0'&&ch<='9')
s=s*10+ch-48,ch=getchar();
return s;
}
void tarjan(int x)
{
dfn[x]=low[x]=++idx;
st[++tp]=x;
for(int i=g.hd[x];i;i=g.e[i].nxt)
{
int v=g.e[i].v;
if(!dfn[v])
{
tarjan(v);
low[x]=min(low[x],low[v]);
if(low[v]==dfn[x])
{
++n;
while(st[tp]^v)
h.add_edge(n,st[tp--]);
h.add_edge(n,st[tp--]);
h.add_edge(x,n);
}
}
else
low[x]=min(low[x],dfn[v]);
}
}
void dfs(int x,int y)
{
st[++tp]=x;
if(x==c)
{
for(int i=1;i<=tp;i++)
vs[st[i]]=1;
return;
}
for(int i=h.hd[x];i;i=h.e[i].nxt)
if(h.e[i].v^y)
dfs(h.e[i].v,x);
--tp;
}
int main()
{
n=read(),m=read(),a=read(),b=read(),c=read();
for(int i=1,u,v;i<=m;i++)
g.add_edge(read(),read());
tarjan(a);
dfs(a,0);
for(int i=h.hd[b];i;i=h.e[i].nxt)
if(vs[h.e[i].v])
return puts("Yes"),0;
puts("No");
}