【C++板块提升计划】梦想护卫舰 第27关 城市与道路

zhangjinxuan

上一关：小船修复

梦想护卫舰 第27关 城市与道路

为什么梦想护卫舰很久都没有都没有更新呢？

因为梦想护卫舰最近听说了海上城市，所以梦想护卫舰也在每天都在航行着，寻找“海上城市”

终于，我们找到了“海上城市”，这个城市有 N 个主要的大楼，编号为 1 ~ N，另外还有 M 条主干道（双行道），主干道 i 连接大楼 u_i 和大楼  v_i

为了更好的了解这个城市，你要帮助他们解决如下问题：

是否每一个互相连通的大楼拥有相同数量的大楼以及主干道

输入格式

1. N M
   
2. u1 v1
   
3. ...
   
4. uM vM

复制代码

输出格式
Yes 或者 No 表示答案

输入样例1

1. 3 3
   
2. 2 3
   
3. 1 1
   
4. 2 3
   

复制代码

输出样例1

1. Yes
   

复制代码

解释：该图有一个仅由小镇 1 形成的互相连通的大楼，另一个由小镇 2 和 3 形成。
前者有一条主干道（2），后者有两条主干道（1和3），因此满足条件。

输入样例2

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

复制代码

输出样例2

1. Yes
   

复制代码

输入样例3

1. 13 16
   
2. 7 9
   
3. 7 11
   
4. 3 8
   
5. 1 13
   
6. 11 11
   
7. 6 11
   
8. 8 13
   
9. 2 11
   
10. 3 3
    
11. 8 12
    
12. 9 11
    
13. 1 11
    
14. 5 13
    
15. 3 12
    
16. 6 9
    
17. 1 10
    

复制代码

输出样例3

1. No
   

复制代码

数据范围
对于 100% 的数据，保证 1 <= n <= 200000，1 <= u, v <= n, 0 <= m <= 200000

                               
登录/注册后可看大图

注：该题非原创，改编于：https://atcoder.jp/contests/abc292/tasks/abc292_d

                               
登录/注册后可看大图

答案与解析

游客，如果您要查看本帖隐藏内容请回复

[/hide]

最佳战士排行榜

	第一名	第二名	第三名
名字
链接
语言
代码得分
奖励	5鱼币5荣誉+“最佳答案”	3鱼币3荣誉	2鱼币2荣誉

我们一起来 Hack

Hack 规则
1. Hack 经证实均有奖励，你在 Hack 时得提供完整证据、证明;
2. 在本关，支持题面 hack，细节问题奖励 1~5 鱼币，重点问题奖励 5~10 鱼币
3. 奖励上限为 3 次

名字	等待着Hack大佬~
Hack 类型
是否证实
链接
奖励

答题/奖励规则
1. 不能抄袭，否则无奖励，可能还会扣分;
2. 当您遇到问题时，您可以回贴提问，我会为您解答
3. 提供完整能得分的题解，均有奖励。
4. 因为额度原因，部分鱼油可能下一天才能奖励。

                               
登录/注册后可看大图

想查看更多精彩内容，请访问 本专辑

创作不易，如果你喜欢，别忘了评分、顶


本关满意度调查

sfqxx

看看思路

sfqxx

不会C++？
python的题解：
注意：我可没说是自己写的！！！！！
@zhangjinxuan 也不知道理解一下在叫！
还扣rating!

1. n,m = list(map(int,input().split()))
   
2. con = [[] for _ in range(n+1)]
   
3. for _ in range(m):
   
4.     u,v = list(map(int,input().split()))
   
5.     con[u].append(v)
   
6.     con[v].append(u)
   
7. idx = [0]*(n+1)
   
8. t = 1
   
9. num = [0]*(n+1)
   
10. for i in range(1,n+1):
    
11.     if idx[i] == 0:
    
12.         idx[i] = t
    
13.         queue = [i]
    
14.         j = 0
    
15.         while j < len(queue):
    
16.             for k in con[queue[j]]:
    
17.                 if idx[k] == 0:
    
18.                     idx[k] = t
    
19.                     queue.append(k)
    
20.             j += 1
    
21.         num[t] = 2*len(queue)
    
22.         t += 1
    
23. #print(num)
    
24. for i in range(1,n+1):
    
25.     for j in con[i]:
    
26.         num[idx[j]] -= 1
    
27. #print(num)
    
28. if num == [0]*(n+1):
    
29.     print('Yes')
    
30. else:
    
31.     print('No')

复制代码

zhangjinxuan

sfqxx 发表于 2023-3-7 19:17
不会C++？
python的题解：

解释一下各个变量是什么，我看不懂

因为现在我评最佳答案的标准还要看思路了

sfqxx

zhangjinxuan 发表于 2023-3-7 19:21
解释一下各个变量是什么，我看不懂

因为现在我评最佳答案的标准还要看思路了

你猜？

zhangjinxuan

sfqxx 发表于 2023-3-7 19:21
你猜？

但是，这代码风也不像你的呀

你不是 n, m 经常大写么
（怀疑度: 30%）

zhangjinxuan

sfqxx 发表于 2023-3-7 19:21
你猜？

你不会是偷偷学了算法吧，这可是高达提高组难度的 bfs 搜索 + 图论哦
（怀疑度：50%）

zhangjinxuan

sfqxx 发表于 2023-3-7 19:21
你猜？

我记得我是说过了的
（怀疑度：90%）



自己说，抄，没，抄？？？！！！！！！！

唉，算了，-20rating起个警示作用吧，为了一个最佳，值得么

唉，算了，给 3 个荣誉意思意思，怕你被扣了 rating 不爽

sfqxx

shift键坏了
（No，Yes为复制）

元豪

sfqxx 发表于 2023-3-7 19:21
你猜？

是不是又是哪个大佬的代码呀

sfqxx

AC一部分的代码

1. n,m = list(map(int,input().split()))
   
2. print("Yes")

复制代码

切

zhangjinxuan

sfqxx 发表于 2023-3-7 19:17
不会C++？
python的题解：
注意：我可没说是自己写的！！！！！

无语.

sfqxx

ok呀，也是成功的被吞帖了

zhangjinxuan

sfqxx 发表于 2023-3-7 20:15
ok呀，也是成功的被吞帖了

我的母语是无语，此时无声胜有声

sfqxx

zhangjinxuan 发表于 2023-3-7 20:34
我的母语是无语，此时无声胜有声

一双玉臂千人枕”、“半点朱唇万客尝

元豪

sfqxx 发表于 2023-3-7 20:40
一双玉臂千人枕”、“半点朱唇万客尝

sfqxx

元豪 发表于 2023-3-7 20:45

zhangjinxuan

sfqxx 发表于 2023-3-7 20:40
一双玉臂千人枕”、“半点朱唇万客尝

So, Y O U W I L L B E L I K E T H E M???
A B A N D O N, M E.....
W I L L Y O U 问号？？？{:10_250:}

歌者文明清理员

zhangjinxuan 发表于 2023-3-7 20:48
So, Y O U W I L L B E L I K E T H E M???
A B A N D O N, M E.....
W I L L Y O U 问号？？？{:10_25 ...

三个问号

zhangjinxuan

歌者文明清理员 发表于 2023-3-7 21:00

这种人我真是表示无语.