社区讨论
题解是否有问题
CF659ENew Reform参与者 1已保存回复 2
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 2 条
- 当前快照
- 1 份
- 快照标识符
- @lo2hunle
- 此快照首次捕获于
- 2023/10/23 14:05 2 年前
- 此快照最后确认于
- 2023/10/23 14:05 2 年前
题干:
一个有很多无向边组成的图,要将无向边改为有向边,但是要求被孤立的点尽量少
如果别的点都不能到达此点,此点就为被孤立点
解法:
如果几个边成环,他们变成单向边后就不会出现被孤立的点
所以题解中使用并查集找环,环中的点就进行标记
最后遍历所有点,如果没有被标记,那它就是一个被孤立的节点
疑惑的点:
题解的意思是,在找环的过程中,如果两个节点的根节点相同,就代表 成环
但是如果两个节点只是根节点相同,应该只是意味着他们联通吧,成环不是意思是从最小的子节点可以直达根节点才能形成闭环嘛?
好吧我是标题党,其实只是我不太理解题解
回复
共 2 条回复,欢迎继续交流。
正在加载回复...