You are given a bunch of wooden sticks. Each endpoint of each stick is colored with some color. Is it possible to align the sticks in a straight line such that the colors of the endpoints that touch are of the same color?
如果我们把不同的颜色看做顶点，对于一条stick，我们把两端的颜色对应的顶点连上边。这道题就是要我们找有没有一条路径只经过所有边一次，这就是欧拉路径的问题。我们在这一篇文章讲过，一个图存在欧拉路径的充要条件是：
- 图是联通的
- 度数为奇数的点为2，其余度数均为偶数
所以在这里我们只需要检查图的这两个性质。鉴于输入的数据量很大，我们用Trie来统计每个颜色节点的度数，Union Find可以帮助我们检查图的联通性。时间复杂度 O(N), N为stick的数量。代码如下：
No comments:
Post a Comment