单行道

shshsh_0510

这题感觉对较大的n很难算，搜索空间太大了$O(2^(n^2))$ 对于一给定的有向图的检测，大体相当于Google的pangrank中求sink，可以参照他的算法。

无心人

解检验原则 对点编号1 -- N^2 假设点，编号A 如果小于A的点到其他点有解 则只要A到A - 1，有解 则A到其他点就有解

gxqcn

咱们两个连举的反例都很类似

无心人

注意 搜索存在优化的 首先图要满足一笔画条件的

shshsh_0510

别老“一笔画”，这个应该是“强连通“有向图

无心人

俺是白菜 不懂图论阿 哈哈

mathe

如下图，下面的图强连通（也就是任何两点之间存在有向路径）， 但是里面不存在哈密顿回路（也就是经过所有点的回路），所以无心人的想法也不可行

无心人

看来3的解多了很多阿 用检验规则作呢？ 首先构造点1的，再点2，再点3 除了1 后面的点 只要保证点N到N-1， 依次类推，就能得到全部解吧 ＝＝＝＝＝＝＝＝＝＝＝＝＝＝ 上午光Build linux Kernel 了 哈哈 reboot检验内核去了

shshsh_0510

检验是否强连通是容易的，我记得好像是“算法导论”，有一个强连通分解算法，好像是用两次深度优先，所以是O(2(m+n))的

mathe

是的，时间复杂度同拓扑排序相同，都是线性时间复杂度。