103186: [Atcoder]ABC318 G - Typical Path Problem
Description
Score : $575$ points
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.
What is a simple path via vertex $Z$?
For vertices $X$ and $Y$ on a graph $G$, a simple path connecting $X$ and $Y$ is a sequence of distinct vertices $(v_1,v_2,\ldots,v_k)$ such that $v_1=X$, $v_k=Y$, and for every integer $i$ satisfying $1\leq i\leq k-1$, there is an edge on $G$ connecting vertices $v_i$ and $v_{i+1}$.A simple path $(v_1,v_2,\ldots,v_k)$ is said to be via vertex $Z$ when there is an $i$ $(2\leq i\leq k-1)$ satisfying $v_i=Z$.
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.
Input
The input is given from Standard Input in the following format:
$N$ $M$ $A$ $B$ $C$ $U_1$ $V_1$ $U_2$ $V_2$ $\vdots$ $U_M$ $V_M$
Output
If there is a simple path that satisfies the condition in the statement, print Yes
; otherwise, print No
.
Sample Input 1
6 7 1 3 2 1 2 1 5 2 3 2 5 2 6 3 4 4 5
Sample Output 1
Yes
One simple path connecting vertices $1$ and $2$ via vertex $3$ is $1$ $\to$ $5$ $\to$ $4$ $\to$ $3$ $\to$ $2$.
Thus, print Yes
.
Sample Input 2
6 6 1 3 2 1 2 2 3 2 5 2 6 3 4 4 5
Sample Output 2
No
No simple path satisfies the condition. Thus, print No
.
Sample Input 3
3 2 1 3 2 1 2 2 3
Sample Output 3
No
Input
Output
得分:$575$分
问题描述
给你一个简单连通无向图$G$,包含$N$个顶点和$M$条边。
顶点和边分别编号为顶点$1$,顶点$2$,$\ldots$,顶点$N$,以及边$1$,边$2$,$\ldots$,边$M$,分别表示,边$i$ $(1\leq i\leq M)$连接顶点$U_i$和$V_i$。
给你图$G$上不同的三个顶点$A$,$B$,$C$。 确定是否存在一条简单路径连接顶点$A$和$C$,经过顶点$B$。
什么是简单连通无向图?
当一个图$G$是一个无向图,且简单且连通时,我们称其为简单连通无向图。当一个图$G$的边没有方向时,我们称其为无向图。
当一个图$G$不包含自环或多边时,我们称其为简单图。
当一个图$G$可以通过边在所有顶点之间旅行时,我们称其为连通图。
什么是经过顶点$Z$的简单路径?
对于图$G$上的顶点$X$和$Y$,连接$X$和$Y$的简单路径是一串不同的顶点$(v_1,v_2,\ldots,v_k)$,满足$v_1=X$,$v_k=Y$,并且对于满足$1\leq i\leq k-1$的任意整数$i$,存在一条连接顶点$v_i$和$v_{i+1}$的边$G$上。当存在一个$ i $ $(2\leq i\leq k-1)$满足$v_i=Z$时,简单路径$(v_1,v_2,\ldots,v_k)$称为经过顶点$Z$。
约束条件
- $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$,和$C$都是不同的。
- $1\leq U_i<V_i\leq N$
- $(U_i,V_i)$对都是不同的。
- 所有输入值都是整数。
输入
输入通过标准输入给出,格式如下:
$N$ $M$ $A$ $B$ $C$ $U_1$ $V_1$ $U_2$ $V_2$ $\vdots$ $U_M$ $V_M$
输出
如果存在满足条件的简单路径,则输出Yes
;否则,输出No
。
样例输入1
6 7 1 3 2 1 2 1 5 2 3 2 5 2 6 3 4 4 5
样例输出1
Yes
连接顶点$1$和$2$,经过顶点$3$的一条简单路径是$1$ $\to$ $5$ $\to$ $4$ $\to$ $3$ $\to$ $2$。
因此,输出Yes
。
样例输入2
6 6 1 3 2 1 2 2 3 2 5 2 6 3 4 4 5
样例输出2
No
不存在满足条件的简单路径。因此,输出No
。
样例输入3
3 2 1 3 2 1 2 2 3
样例输出3
No