题解：P9739 [COCI2022-2023#2] Kruhologija（征集交互库）

· · 题解

写一下官方题解的思路。

首先根据欧拉示性数相关内容可以用边数(E)，面数(F)与点数(V)算出洞(g)的数量：

V-E+F=2-2g

其中 E 和 F 都是好求出的。F 我们做一次dfs即可求出，而由于每个面度数为 4，总边数为 2F。

现在关键问题是如何求出点的个数。我们发现所有点分为 3,4,5 度三种。而当我们到达一个面的时候，通过不断地转向，前进这个组合，记录下多少次回到自己，就可以求出这个端点的度数，正确性是显然的。那么我们在按照这种方法对于每个面求出它四个端点的个数即可求出总点数。

我自己写的唐氏交互库