社区讨论

题解是否有问题

CF659ENew Reform参与者 1已保存回复 2

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@lo2hunle
此快照首次捕获于
2023/10/23 14:05
2 年前
此快照最后确认于
2023/10/23 14:05
2 年前
查看原帖

题干:

一个有很多无向边组成的图,要将无向边改为有向边,但是要求被孤立的点尽量少
如果别的点都不能到达此点,此点就为被孤立点

解法:

如果几个边成环,他们变成单向边后就不会出现被孤立的点
所以题解中使用并查集找环,环中的点就进行标记
最后遍历所有点,如果没有被标记,那它就是一个被孤立的节点

疑惑的点:

题解的意思是,在找环的过程中,如果两个节点的根节点相同,就代表 成环
但是如果两个节点只是根节点相同,应该只是意味着他们联通吧,成环不是意思是从最小的子节点可以直达根节点才能形成闭环嘛?

好吧我是标题党,其实只是我不太理解题解

回复

2 条回复,欢迎继续交流。

正在加载回复...