#D. 修改用户名

    传统题 2000ms 256MiB

修改用户名

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

小赛码运营的Web服务有N N 的用户。每个用户有一个用户名 SiS_i 现在每个用户都想改成另一个用户名 TiT_i,如果一个用户想要改的名字没有人正在用,那么这个用户可以改名。现在用户改名的顺序由你决定,请问是否所有用户都可以成功改名。注意每个人现在只有一次修改的机会。

输入格式

输入格式如下

N N

S1 S_1 T1 T_1

S2 S_2 T2 T_2

...... ......

SN S_N TN T_N

输出格式

当所有用户的用户名能够按希望变更时Yes,当不能变更时No,以满足所有条件。

样例 #1

样例输入 #1

2
b m
m d

样例输出 #1

Yes

样例 #2

样例输入 #2

3
a b
b c
c a

样例输出 #2

No

样例 #3

样例输入 #3

5
aaa bbb
yyy zzz
ccc ddd
xxx yyy
bbb ccc

样例输出 #3

Yes

数据范围与提示

1  N  105 1\ \leq\ N\ \leq\ 10^5 si,ti s_i, t_i 是由英文小写字母组成的1 1 字符以上8 8 字符以下的字符串

  • si  ti s_i \ \neq\ t_i
  • si s_i 是不同的
  • ti t_i 不同

样例 1 解释

1 1 用户的当前用户名是b,希望更改为m。第2 2 用户的当前用户名是m,希望更改为d。首先,将第2 2 用户的用户名从m改为d,然后将第1 1 用户的用户名从b改为m的变更,可以在满足条件的同时进行变更。在最初的时候,第2 2 的用户的用户名是m,所以不能将第1 1 的用户的用户名改为相同的m

样例 2 解释

1 1 用户的当前用户名是a,希望更改为b。第2 2 用户的当前用户名是b,希望更改为c。第3 3 用户的当前用户名是c,希望更改为a。不能一边满足条件一边进行用户名的变更。

【CQMC】重庆小码王C++月赛 - 算法组 #3

未参加
状态
已结束
规则
IOI
题目
4
开始于
2024-1-20 9:00
结束于
2024-1-22 0:00
持续时间
39 小时
主持人
参赛人数
58