【题目大意】
给定一个无向图，把每条边黑白染色，使得所有的度大于等于2的点有至少有一条黑边和一条白边相连。
【算法分析】
很久之前写过随机算法过了，现在贴一个构造法的。
其实主要是update函数非常精髓。
首先构建dfs树，无向图dfs树具有的一大优点是该点只会向自己的祖先或子孙有非树边。
然后按深度交替染色。返祖边与自己的儿子涂同样的颜色。
如果dfs树中根结点度超过1，那么就找一条边染不同的颜色。
否则看根结点是否满足条件，如果不是，那么找一个与根结点相连的叶子，向上找到一个度大于2的点为止，将该路径上所以边反色，并且将根与该叶子的边反色。如果找不到度大于2的点，那么是奇环，无解。
【CODE】
C++ CODE :SGU121 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99100101 #include