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

zhangjinxuan

上一关：小船修复

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

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

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

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

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

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

输入格式

N M
u1 v1
...
uM vM

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

输入样例1

3 3
2 3
1 1
2 3

输出样例1

Yes

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

输入样例2

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

输出样例2

Yes

输入样例3

13 16
7 9
7 11
3 8
1 13
11 11
6 11
8 13
2 11
3 3
8 12
9 11
1 11
5 13
3 12
6 9
1 10

输出样例3

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!

n,m = list(map(int,input().split()))
con = [[] for _ in range(n+1)]
for _ in range(m):
    u,v = list(map(int,input().split()))
    con[u].append(v)
    con[v].append(u)
idx = [0]*(n+1)
t = 1
num = [0]*(n+1)
for i in range(1,n+1):
    if idx[i] == 0:
        idx[i] = t
        queue = [i]
        j = 0
        while j < len(queue):
            for k in con[queue[j]]:
                if idx[k] == 0:
                    idx[k] = t
                    queue.append(k)
            j += 1
        num[t] = 2*len(queue)
        t += 1
#print(num)
for i in range(1,n+1):
    for j in con[i]:
        num[idx[j]] -= 1
#print(num)
if num == [0]*(n+1):
    print('Yes')
else:
    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一部分的代码

n,m = list(map(int,input().split()))
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

这种人我真是表示无语.