题目详情题解（0）讨论（0）提交记录（0）

AT_past19_f.ドミノ倒し

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

你正在摆放多米诺骨牌。

有 NN 条线索：对于每个 1≤i≤N1 \leq i \leq N，如果多米诺骨牌 SiS_i 倒下，那么多米诺骨牌 TiT_i 也会倒下。

请判断给定的线索是否能够推出：如果多米诺骨牌 XX 倒下，那么多米诺骨牌 YY 也会倒下。

输入格式

输入通过标准输入给出，格式如下：

N X Y S1 T1 ⋮ SN TNN\ X\ Y\ S_1\ T_1\ \vdots\ S_N\ T_N

输出格式

如果已知线索能够推出“如果多米诺骨牌 XX 倒下，则 YY 也会倒下”，请输出 Yes；否则输出 No。

输入输出样例

  • 输入#1

    5
second fourth
first second
second third
third fourth
fourth fifth
fifth sixth

    输出#1

    Yes

  • 输入#2

    5
fourth second
first second
second third
third fourth
fourth fifth
fifth sixth

    输出#2

    No

  • 输入#3

    6
e d
a b
b a
a c
c d
d e
e a

    输出#3

    Yes

  • 输入#4

    1
a b
x y

    输出#4

    No

说明/提示

样例解释 1

第二条线索表明，如果骨牌 second 倒下，则骨牌 third 也会倒下；第三条线索又说明，如果骨牌 third 倒下，则骨牌 fourth 也会倒下。因此，我们可以推断，如果骨牌 second 倒下，则骨牌 fourth 也会倒下。

样例解释 2

无法从给定的线索推出“如果骨牌 fourth 倒下，则骨牌 second 也会倒下”。

数据范围

  • 1≤N≤2×1051 \leq N \leq 2\times 10^5
  • NN 是整数。
  • 每个 Si,Ti,X,YS_i, T_i, X, Y 都是长度在 11 到 100100 之间的字符串，仅包含小写英文字母。
  • X≠YX \neq Y
  • 对所有 ii，都有 Si≠TiS_i \neq T_i。
  • 对所有 (Si,Ti)(S_i, T_i) 都不相同。

由 ChatGPT 5 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页