UVA 10054 The Necklace

题意

给出若干二色珠子,问你能不能把他们重新排列以连成一条环,使得相邻的两个珠子颜色相同。

思路

转化为欧拉图问题。令结点代表不同的颜色,连接两个结点的边代表珠子。把珠子连成项链的过程转化为求出一种走法使得我们可以走完全部的边然后返回起点。这就是典型的欧拉回路问题了。

如果不会这个知识,请参考:有关欧拉图问题的一些总结

代码

 

欧拉图和哈密顿图小总结

欧拉图

概念

定义

欧拉回路:图中经过每条边一次且仅一次的环;
欧拉路径:图中经过每条边一次且仅一次的路径;
欧拉图:有至少一个欧拉回路的图;
半欧拉图:没有欧拉环,但有至少一条欧拉路径的图。

无向图判定条件

  • 图是联通的(度数为0的点不用考虑,因为是孤立的点,没影响)~先决条件
  • 所有点的度数都是偶数~存在欧拉回路,欧拉图
  • 有且仅有两个点的度数是奇数~存在欧拉路径,半欧拉图
    两个奇数度数的点一个是路径起点一个是路径终点

证明:因为任意一个点,欧拉环(或欧拉路径)从它这里进去多少次就要出来多少次,故(进去的次数+出来的次数)为偶数,又因为(进去的次数+出来的次数)=该点的度数(根据定义),所以该点的度数为偶数。

有向图判定条件

  • 把所有的边强行改为无向边之后(这个图叫原图的基图),联通~先决条件
  • 所有点出度等于入度~存在欧拉回路,欧拉图
  • 有且仅有两个点出度不等于入度,一个出度比入度大1,另一个入度比出度大1~欧拉路径,半欧拉图
    出度比入度大1的点是路径起点,入度比出度大1的点是路径终点

证明:与无向图证明类似,一个点进去多少次就要出来多少次。

模板

 

Scroll to top