后知后觉10个包子求一个saks20%，今天是最后一天了？ - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Fashion - 美丽时尚

后知后觉10个包子求一个saks20%，今天是最后一天了？

后知后觉10个包子求一个saks20%，今天是最后一天了？# Fashion - 美丽时尚

W*y2012-12-10 08:12

1 楼

准备一个一维数组存每个点的parent，另外一个一维数组记录是否访问过。
先找in-degree = 0的点，然后dfs，遍历时候记录每个点的parents，记录访问情况
如果是环，任意取一点dfs，同样记录每个点的parents，记录访问情况
最后用union find 找到最终root，然后数不同root的个数。
这样方法是否可行，看到有人说必须用strong-connect component，不知为何，还望举
例说明

q*62012-12-10 08:12

2 楼

谢谢哈，穷人，只有这么多包子哈，有的妹妹短我哈

r*s2012-12-10 08:12

3 楼

没有特别看清楚lz对于环指向环的情况是怎么处理的
感觉这样做下去最终就收敛回强连通了。。

W*y2012-12-10 08:12

4 楼

已经更新题目，，

【在 r*****s 的大作中提到】

: 没有特别看清楚lz对于环指向环的情况是怎么处理的
: 感觉这样做下去最终就收敛回强连通了。。

z*n2012-12-10 08:12

5 楼

lz标题应该叫最少点，不是最小点吧。。
读了3遍lz算法才猜出来题目是啥。是说最少需要几个起点，就能dfs遍历一个有向图的
所有点，是这意思吗？
如果是这个意思，那应该确实跟SCC没啥关系，反例很简单。一个图:A->B。这里有俩
SCC，但一个root A就能遍历全图。
如果我没理解错lz意思，那下面这么做应该就行了，不需要什么union find，写起来多
麻烦。
1.DFS整个图，按每个点的完成顺序存下每个点。类似拓扑排序
2.按记录顺序的逆序开始DFS整个图，每一个新的起点都是一个root。

y*u2012-12-10 08:12

6 楼

正解。zengqinghan兄还是厉害，吻你

【在 z*********n 的大作中提到】

: lz标题应该叫最少点，不是最小点吧。。
: 读了3遍lz算法才猜出来题目是啥。是说最少需要几个起点，就能dfs遍历一个有向图的
: 所有点，是这意思吗？
: 如果是这个意思，那应该确实跟SCC没啥关系，反例很简单。一个图:A->B。这里有俩
: SCC，但一个root A就能遍历全图。
: 如果我没理解错lz意思，那下面这么做应该就行了，不需要什么union find，写起来多
: 麻烦。
: 1.DFS整个图，按每个点的完成顺序存下每个点。类似拓扑排序
: 2.按记录顺序的逆序开始DFS整个图，每一个新的起点都是一个root。

y*u2012-12-10 08:12

7 楼

等等，难道这个算出的不是SCC？
1.DFS整个图，按每个点的完成顺序存下每个点。类似拓扑排序
2.按记录顺序的逆序开始DFS整个图，每一个新的起点都是一个root

【在 z*********n 的大作中提到】

z*n2012-12-10 08:12

8 楼

不是。。。SCC得做transpose graph。。还是叫补图，还是叫反图那个

【在 y**********u 的大作中提到】

: 等等，难道这个算出的不是SCC？
: 1.DFS整个图，按每个点的完成顺序存下每个点。类似拓扑排序
: 2.按记录顺序的逆序开始DFS整个图，每一个新的起点都是一个root

r*s2012-12-10 08:12

9 楼

对啊，这算法不就是SCC吗。。。。

: 等等，难道这个算出的不是SCC？

: 1.DFS整个图，按每个点的完成顺序存下每个点。类似拓扑排序

: 2.按记录顺序的逆序开始DFS整个图，每一个新的起点都是一个root

【在 y**********u 的大作中提到】

r*s2012-12-10 08:12

10 楼

啊翻算法导论去了。。。

: 不是。。。SCC得做reverse graph。。还是叫补图，还是叫反图那个

【在 z*********n 的大作中提到】

:
: 不是。。。SCC得做transpose graph。。还是叫补图，还是叫反图那个

y*u2012-12-10 08:12

11 楼

我读书少，zengqinghan兄别骗我……

【在 z*********n 的大作中提到】

:
: 不是。。。SCC得做transpose graph。。还是叫补图，还是叫反图那个

W*y2012-12-10 08:12

12 楼

例子：edges:a->b, b->c, b->d。 a的indegree=0，是dfs的起点
按完成顺序是[c,d,b,a]或者[d,c,b,a]
在按照记录顺序的逆序走一遍，不是还是原来的dfs么？
而且这个方法很像强连通，除了你没有翻转edge的方向。

【在 z*********n 的大作中提到】

W*y2012-12-10 08:12

13 楼

大概懂你意思了，第一遍dfs遍历，类似于做了个toposort，因为第一遍时候你无法确
定没有visited的点是一个新的起点还是一个在path上的点
第二遍遍历的时候因为已经toposort过了。没有visited的点肯定是一个新的起点。
这个好厉害。。。

【在 z*********n 的大作中提到】

z*n2012-12-10 08:12

14 楼

是“原来”的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*y2012-12-10 08:12

15 楼

了解了，，这方法好巧啊。。

【在 z*********n 的大作中提到】

:
: 是“原来”的DFS，你所谓的“原来”是你根据indegree人脑找出了一个最合理的起
: 点，其实就是问题的最终解了，这个算法能做出来这个解，不正好说明它是对的么？
: 但你注意，我这算法里没有算indegree这步，可能我“原来”的dfs起点是c啊，或者是
: b啊，你看看结果是不是也是你那个“原来”的dfs