[ABC318G] Typical Path Problem 题解

原题链接：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;
}