Typical Path Problem

题目描述

你被给定了一个具有 $N$ 个顶点和 $M$ 条边的简单连通无向图 $G$。
图 $G$ 的顶点与边分别编号为 顶点 $1$、顶点 $2$、$\ldots$、顶点 $N$，以及 边 $1$、边 $2$、$\ldots$、边 $M$，并且第 $i$ 条边 $(1\leq i\leq M)$ 连接顶点 $U_i$ 和 $V_i$。
还给定了图 $G$ 上互不相同的顶点 $A,B,C$。 判断是否存在一条通过顶点 $B$ 的连接顶点 $A$ 和 $C$ 的简单路径。

输入格式

输入由标准输入按以下格式给出： $N$ $M$ $A$ $B$ $C$ $U_1$ $V_1$ $U_2$ $V_2$ $\vdots$ $U_M$ $V_M$

输出格式

如果存在满足题意的简单路径，输出 $Yes$；否则，输出 $No$。

6 7
1 3 2
1 2
1 5
2 3
2 5
2 6
3 4
4 5

Yes

6 6
1 3 2
1 2
2 3
2 5
2 6
3 4
4 5

No

3 2
1 3 2
1 2
2 3

No

提示

$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)$ 成对都互不相同。 所有输入值均为整数。一条连接顶点 $1$ 和 $2$ 且经过顶点 $3$ 的简单路径为 $1$ $\to$ $5$ $\to$ $4$ $\to$ $3$ $\to$ $2$。 因此，输出 $Yes$。
没有简单路径满足条件。因此，输出 $No$。

标签: AtCoder|abc318G

来源

AtCoder|abc318G