随仙人掌方法

· · 个人记录

感谢传奇特级大师 liuhengxi 的指导。

先随一些环和点,再把这些环和点连起来。连接环与环表现为合并两个环上的随机点,连接环与点和点与点则为在两者间连边。合并完成后对点重标号即可。

如果初始有 n 个环和点,则连接过程相当于一个 n 个点的树,可以通过隐式地随一棵树的方式确定合并过程。

合并两个点容易用并查集实现。

初始随的环可以既有大环又有小环,增加强度。

另一种方法:

感谢传奇特级大师 liuhengxi 的指导。

随一棵树,然后取一个独立集作为方点。随独立集可以先 shuffle 点的顺序,然后按顺序扫,能取的点以某个概率取。

更专业一点的方法