22.4-1:
不得不说老外有时候也挺变态的,搞这么复杂个图...考概念你把图弄小点啊,考这么大,吓死我这种刚入门的小菜鸟小朋友咋办
写纸上了略了,耐心点就好

22.4-2:
开始觉得是深搜,试了一下不行
然后联想到这节讲的就是拓排...肯定得用拓排啦(填鸭式教育的思维啊...)
不过还是没想出来线性算法,到处搜答案...汗,一搜搜到斯坦福的一篇作业讲解,牛叉学校果然不一样
看的结果是——动态规划...
看来DP快点上手了

演示图(标记为数字的完全是为方便DFS时候的顺序,假设同22.3-2)
(1)拓排,即可得类似P336,图22-7所示的从左到右的一个顺序关系,即上图下部分的样子
(2)DP一下
记P[v]为s到v的路径数,初始化为0
把P[p]设为1
P[v]=(u,v)belongs to EP[u]
也就是说等于所有拓扑序前面的与之相边的顶点的P[]之和
复杂度为:
拓排: O(V+E)
左到右扫一遍DP:V
所以为O(V+E)

不明白的地方:用啥数据结构表示呢?
A:邻接表...
http://www-cs-students.stanford.edu/phd/comps/2007/2007-Analysis_of_Algorithms-solutions.pdf

22.4-3: