【交叉染色法判断二分图】Claw Decomposition UVA - 11396
题目链接:https://cn.vjudge.net/contest/209473#problem/C先谈一下二分图相关:一个图是二分图的充分必要条件: 该图对应无向图的所有回路必定是偶环(构成该环形的边的数量为偶数)。暂时不证明,后证。那么怎么判断一个图的回路是奇环还是偶环呢?交叉染色法。随机选择一个点,染成红色,把所有跟它相邻的点染成绿色,再由被染色的...