> 先找出连通块，对每一个连通块，如果该连通块含奇回路，那么该连通块的所有点都可行。
> 这样找奇回路：从任一点开始进行标号，如果某节点被标为1，则与之相邻的将被标为2。反之亦然。如果有点既被标为1，又被标为2，那么，该连通块含奇回路。


一个块若无法做二分图染色，势必存在一个长度为奇数的环
任找一个奇环C，则对于任意一个非环上的点A，一定有两条不相交的路，连向这个奇环，交奇环于两个不同的点P、Q（否则这就不是一个双连通分量）

那么在环C上有两条P-->Q的路径，一条经过奇数条边，一条经过偶数条边
其中一条同PA、AQ相连后，一定是个奇环，所以A一定也在一个奇环上
 膜拜AlNo3，这段话写得很好。 

• Re:请教该算法的正确性（我好像可以证明，但一直WA），感激不尽 (121) llx2192716 2011-03-08 18:34:31
• Re:请教该算法的正确性（我好像可以证明，但一直WA），感激不尽 (212) lowever 2012-03-19 14:55:55