原题链接：ABC318G
显然是圆方树。
点双缩点过后建立一颗以点 \(c\) 为根节点的圆方树，考虑什么情况是合法的。
从点 \(a\) 开始往上跳直到跳到点 \(c\)，如果中间走过了某一个方点并且这个方点与 \(b\) 点有直接连边，那么就是合法的；否则不合法。
证明：如果路径中所经过的方点和 \(b\) 点有直接连边的话，那就说明了点 \(b\) 和路径上的一个点在同一个点双连通分量当中。所以一定可以通过一种路径来实现经过 \(b\) 点。
Code
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define inf 0x3f
#define inf_db 127
#define ls id << 1
#define rs id << 1 | 1
#define re register
#define endl '\n'
typedef pair <int,int> pii;
const int MAXN = 1e6 + 10;
int n,m,head[MAXN],cnt,x,y,root,a,b,c,Cnt,Head[MAXN],fa[MAXN];
int dfn[MAXN],low[MAXN],id[MAXN],dcc_cnt,timestamp;
vector <int> dcc[MAXN];
struct Node
{
int u,v,nxt;
}e[MAXN];
struct Edge
{
int u,v,nxt;
}g[MAXN];
inline void Add(int u,int v){e[++cnt] = {u,v,head[u]};head[u] = cnt;}
inline void add(int u,int v){g[++Cnt] = {u,v,Head[u]};Head[u] = Cnt;}
stack <int> s;
inline void Tarjan(int u,int father)
{
dfn[u] = low[u] = ++timestamp;
s.push(u);int son = 0;
for(int i = head[u]; ~ i;i = e[i].nxt)
{
int now = e[i].v;
if(!dfn[now])
{
Tarjan(now,u),low[u] = min(low[u],low[now]),son++;
if(dfn[u] <= low[now])
{
int y;dcc_cnt++;
do
{
y = s.top();s.pop();
id[y] = dcc_cnt;
dcc[dcc_cnt].push_back(y);
}while(y != now);
dcc[dcc_cnt].push_back(u);
}
}
else if(now != father) low[u] = min(low[u],dfn[now]);
}
if(son == 0 && u == root) dcc[++dcc_cnt].push_back(u);
}
inline void Dfs(int u,int father)
{
fa[u] = father;
for(int i = Head[u]; ~ i;i = g[i].nxt)
{
int now = g[i].v;
if(now == father) continue;
Dfs(now,u);
}
}
inline bool Check(int u)
{
for(int i = u;i != c;i = fa[i])
if(i > n) for(int j = Head[i]; ~ j;j = g[j].nxt) if(b == g[j].v) return true;
return false;
}
signed main()
{
memset(head,-1,sizeof head);
memset(Head,-1,sizeof Head);
cin >> n >> m >> a >> b >> c;
for(int i = 1;i <= m;i++) cin >> x >> y,Add(x,y),Add(y,x);
for(root = 1;root <= n;root++) if(!dfn[root]) Tarjan(root,0);
int num = n;
for(int i = 1;i <= dcc_cnt;i++)
{
int k = ++num;
for(int j = 0;j < dcc[i].size();j++) add(k,dcc[i][j]),add(dcc[i][j],k);
}
Dfs(c,0);
cout << (Check(a) ? "Yes" : "No");
return 0;
}