W**********y
发帖数: 85 | 1 准备一个一维数组存每个点的parent，另外一个一维数组记录是否访问过。
先找in-degree = 0的点，然后dfs，遍历时候记录每个点的parents，记录访问情况
如果是环，任意取一点dfs，同样记录每个点的parents，记录访问情况
最后用union find 找到最终root，然后数不同root的个数。
这样方法是否可行，看到有人说必须用strong-connect component，不知为何，还望举
例说明 |
r*****s
发帖数: 1815 | 2 没有特别看清楚lz对于环指向环的情况是怎么处理的
感觉这样做下去最终就收敛回强连通了。。 |
W**********y
发帖数: 85 | 3 已经更新题目，，
【在 r*****s 的大作中提到】
: 没有特别看清楚lz对于环指向环的情况是怎么处理的
: 感觉这样做下去最终就收敛回强连通了。。
|
z*********n
发帖数: 1451 | 4 lz标题应该叫最少点，不是最小点吧。。
读了3遍lz算法才猜出来题目是啥。是说最少需要几个起点，就能dfs遍历一个有向图的
所有点，是这意思吗？
如果是这个意思，那应该确实跟SCC没啥关系，反例很简单。一个图:A->B。这里有俩
SCC，但一个root A就能遍历全图。
如果我没理解错lz意思，那下面这么做应该就行了，不需要什么union find，写起来多
麻烦。
1.DFS整个图，按每个点的完成顺序存下每个点。类似拓扑排序
2.按记录顺序的逆序开始DFS整个图，每一个新的起点都是一个root。 |
y**********u
发帖数: 2839 | 5 正解。zengqinghan兄还是厉害，吻你
【在 z*********n 的大作中提到】
: lz标题应该叫最少点，不是最小点吧。。
: 读了3遍lz算法才猜出来题目是啥。是说最少需要几个起点，就能dfs遍历一个有向图的
: 所有点，是这意思吗？
: 如果是这个意思，那应该确实跟SCC没啥关系，反例很简单。一个图:A->B。这里有俩
: SCC，但一个root A就能遍历全图。
: 如果我没理解错lz意思，那下面这么做应该就行了，不需要什么union find，写起来多
: 麻烦。
: 1.DFS整个图，按每个点的完成顺序存下每个点。类似拓扑排序
: 2.按记录顺序的逆序开始DFS整个图，每一个新的起点都是一个root。
|
y**********u
发帖数: 2839 | 6 等等，难道这个算出的不是SCC？
1.DFS整个图，按每个点的完成顺序存下每个点。类似拓扑排序
2.按记录顺序的逆序开始DFS整个图，每一个新的起点都是一个root
【在 z*********n 的大作中提到】
: lz标题应该叫最少点，不是最小点吧。。
: 读了3遍lz算法才猜出来题目是啥。是说最少需要几个起点，就能dfs遍历一个有向图的
: 所有点，是这意思吗？
: 如果是这个意思，那应该确实跟SCC没啥关系，反例很简单。一个图:A->B。这里有俩
: SCC，但一个root A就能遍历全图。
: 如果我没理解错lz意思，那下面这么做应该就行了，不需要什么union find，写起来多
: 麻烦。
: 1.DFS整个图，按每个点的完成顺序存下每个点。类似拓扑排序
: 2.按记录顺序的逆序开始DFS整个图，每一个新的起点都是一个root。
|
z*********n
发帖数: 1451 | 7
不是。。。SCC得做transpose graph。。还是叫补图，还是叫反图那个
【在 y**********u 的大作中提到】
: 等等，难道这个算出的不是SCC？
: 1.DFS整个图，按每个点的完成顺序存下每个点。类似拓扑排序
: 2.按记录顺序的逆序开始DFS整个图，每一个新的起点都是一个root
|
r*****s
发帖数: 1815 | 8 对啊，这算法不就是SCC吗。。。。
: 等等，难道这个算出的不是SCC？
: 1.DFS整个图，按每个点的完成顺序存下每个点。类似拓扑排序
: 2.按记录顺序的逆序开始DFS整个图，每一个新的起点都是一个root
【在 y**********u 的大作中提到】
: 等等，难道这个算出的不是SCC？
: 1.DFS整个图，按每个点的完成顺序存下每个点。类似拓扑排序
: 2.按记录顺序的逆序开始DFS整个图，每一个新的起点都是一个root
|
r*****s
发帖数: 1815 | 9 啊 翻算法导论去了。。。
: 不是。。。SCC得做reverse graph。。还是叫补图，还是叫反图那个
【在 z*********n 的大作中提到】
:
: 不是。。。SCC得做transpose graph。。还是叫补图，还是叫反图那个
|
y**********u
发帖数: 2839 | 10 我读书少，zengqinghan兄别骗我……
【在 z*********n 的大作中提到】
:
: 不是。。。SCC得做transpose graph。。还是叫补图，还是叫反图那个
|
W**********y
发帖数: 85 | 11 例子：edges:a->b, b->c, b->d。 a的indegree=0，是dfs的起点
按完成顺序是[c,d,b,a]或者[d,c,b,a]
在按照记录顺序的逆序走一遍，不是还是原来的dfs么？
而且这个方法很像强连通，除了你没有翻转edge的方向。
【在 z*********n 的大作中提到】
: lz标题应该叫最少点，不是最小点吧。。
: 读了3遍lz算法才猜出来题目是啥。是说最少需要几个起点，就能dfs遍历一个有向图的
: 所有点，是这意思吗？
: 如果是这个意思，那应该确实跟SCC没啥关系，反例很简单。一个图:A->B。这里有俩
: SCC，但一个root A就能遍历全图。
: 如果我没理解错lz意思，那下面这么做应该就行了，不需要什么union find，写起来多
: 麻烦。
: 1.DFS整个图，按每个点的完成顺序存下每个点。类似拓扑排序
: 2.按记录顺序的逆序开始DFS整个图，每一个新的起点都是一个root。
|
W**********y
发帖数: 85 | 12 大概懂你意思了，第一遍dfs遍历，类似于做了个toposort，因为第一遍时候你无法确
定没有visited的点是一个新的起点还是一个在path上的点
第二遍遍历的时候因为已经toposort过了。没有visited的点肯定是一个新的起点。
这个好厉害。。。
【在 z*********n 的大作中提到】
: lz标题应该叫最少点，不是最小点吧。。
: 读了3遍lz算法才猜出来题目是啥。是说最少需要几个起点，就能dfs遍历一个有向图的
: 所有点，是这意思吗？
: 如果是这个意思，那应该确实跟SCC没啥关系，反例很简单。一个图:A->B。这里有俩
: SCC，但一个root A就能遍历全图。
: 如果我没理解错lz意思，那下面这么做应该就行了，不需要什么union find，写起来多
: 麻烦。
: 1.DFS整个图，按每个点的完成顺序存下每个点。类似拓扑排序
: 2.按记录顺序的逆序开始DFS整个图，每一个新的起点都是一个root。
|
z*********n
发帖数: 1451 | 13
是“原来”的DFS，你所谓的“原来”是你根据indegree人脑找出了一个最合理的起
点，其实就是问题的最终解了，这个算法能做出来这个解，不正好说明它是对的么？
但你注意，我这算法里没有算indegree这步，可能我“原来”的dfs起点是c啊，或者是
b啊，你看看结果是不是也是你那个“原来”的dfs
【在 W**********y 的大作中提到】
: 例子：edges:a->b, b->c, b->d。 a的indegree=0，是dfs的起点
: 按完成顺序是[c,d,b,a]或者[d,c,b,a]
: 在按照记录顺序的逆序走一遍，不是还是原来的dfs么？
: 而且这个方法很像强连通，除了你没有翻转edge的方向。
|
W**********y
发帖数: 85 | 14 了解了，，这方法好巧啊。。
【在 z*********n 的大作中提到】
:
: 是“原来”的DFS，你所谓的“原来”是你根据indegree人脑找出了一个最合理的起
: 点，其实就是问题的最终解了，这个算法能做出来这个解，不正好说明它是对的么？
: 但你注意，我这算法里没有算indegree这步，可能我“原来”的dfs起点是c啊，或者是
: b啊，你看看结果是不是也是你那个“原来”的dfs
|
