一种基于耳分解的双连通图数据生成方案

· · 算法·理论

原谅我把标题起的这么高大上（

相信大家都出过图论题，而图论题往往与双连通分量密不可分。在造此类数据时，你可能会遇到这样的问题：我需要控制这个图的每个双连通分量的性质，同时还需要保证边数，这听上去就很困难！那么有没有什么好的解决方法呢？

以点双为例。容易发现：一个无向图是点双连通的，当且仅当其存在一组开耳分解。而恰巧的是：若该图的耳分解中有 k 个开耳，那么每个耳都会贡献恰好一条边！这样我们就控制了一个分量点双连通。

所以具体生成过程如下：

  1. 确定点数 n 边数 m。
  2. 将 n 个点划分为 m-n+1 组。
  3. 将第一组作为一个环加入，之后依次将每一组作为一个开耳加入图中。
  4. 打乱标号。

这样就可以在生成一个点双连通图并同时控制边数了。修改一下就能变成点双联通甚至有向图强连通。而且由于 testlib 中预设了 partition 和 shuffle，这东西实现起来也异常简单。