[SGU121 Bridges painting]【构造法】

【题目大意】

给定一个无向图,把每条边黑白染色,使得所有的度大于等于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

留下评论

您的电子邮箱地址不会被公开。