摘要: 题目要求统计一个平面图中所有边数为k的面的个数。应该是个经典问题。说说我的算法吧。
枚举每条边，做以下的基本步骤。
基本步骤：以这条边作起始边，不断地找下一条“最左转”的边，并且标记每个点的访问次数，直到某个点第3次被访问为止。
经过这个步骤之后，得到一个顶点序列。容易知道，当且仅当这个顶点序列是2-重复（就是形如12341234这样），并且是逆时针旋转的，那么就是一个面。
接下去我们就把所有找到的边数为k面进行hash去重，就得到答案啦。
貌似我想的这个算法不够好，如果有更好的算法，欢迎和我讨论。
阅读全文