注意到此题一定无环(不清楚的请再读几遍题)，所以可以动态规划的递推式传递。即令F[i]表示i比哪些大的集合，可通过i所连向的点的F值来更新，不过，不太优美的是更新复杂度是O(N),如果N再小一些的话是可以用位运算做到O(1)的，很遗憾的。那么，对于每个点的更新次数为所连向边的条数*(N).所以总次数为O(M*N).
统计时只需看看大于点i的数量加小于点i的数量是否为N-1即可。总复杂度(M*N+N*N).
应该比传递闭包的复杂度小一些吧，呵呵。 抛砖引玉，希望有大牛提出更好的方法，最好讲详细一些～

• Re:试题分析 (27) lvcheng 2010-04-10 11:30:39