基本正确, 但染色是最重要的一步. 因为染色会帮你去掉很多以前算法已经算过的重复
的状态. 如果不染色的话, 复杂度会提高很多. 可能 s 能到达的点构成一个图 G1, 比如大小是 |V| 的一半, 剩下的图 G2 是个强连通
分量, 并且有一条边是从 G2 指向 G1 的. 如果不染色, 你首先会算 G1 是否有负环, 然后到了 G2, 程序除了会算 G2 是否有负环外, 
还会通过 G2 到 G1 的那条有向边进入 G1, 再算一遍 G1 的子图(可能就是G1)是否有负环, 这样就等于做了无用功, 因为 G1 没有负
环, G1 的子图自然也没有.这样总的复杂度就极有可能超过 O(V^3). 而加了染色, 正如我前面的回复中所分析的, 复杂度最多为
O(V^3). 从这个例子很容易看出复杂度的差别.

PS:这还是我第一次回复别人的问题...真是多谢你的理解力, 让我有了充分的信心:)

• Re:你这复杂度是闹哪样... (51) jwpan 2012-07-19 23:20:53