CF329C Graph Reconstruction 题解

题意：

给定一张含有 $n$ 个点 $m$ 条边的无向简单图 $G = \left( V, E \right)$，其中每个顶点的度数不超过 $2$。你需要构造一张新的无向简单图 $G’ = \left( V’, E’ \right)$，满足如下条件：

$V’ = V, \left| E’ \right| = \left| E \right| = m$。

$E’ \cap E = \varnothing$ ，即原图和新图中没有公共的边。

$\Delta(G’) \le 2$，即新的图中每个顶点的度数均不超过 $2$。

注：其中 $\Delta (G)$ 表示的是图 $G$ 的最大度，下文中出现的 $\delta(G)$ 表示的是图 $G$ 的最小度。

输出任何一个满足上述三个条件的图 $G’$，或指出不存在。

输入格式：

第一行包含两个正整数 $n, m(1 \leq m \leq n \leq 10^5)$，表示图 $G$ 的点数和边数。

接下来的 $m$ 行，每行两个正整数 $u, v(1 \leq u, v \leq n, u \neq v)$，表示 $u$ 和 $v$ 之间有一条边相连。

输出格式：

如果不存在满足条件的图 $G’$，则输出一行一个整数 $-1$ 。

否则，输出 $m$ 行，每行两个正整数 $u, v$，描述 $G’$ 中的一条边。

前置知识：Dirac定理（狄拉克定理）、Hamilton 回路等

可能会用到的参考资料：图论相关概念（~~鬼知道为了写这题补了多少前置知识~~）

考虑度数不超过 $2$ 的图有什么性质。不难发现，这个图一定由若干个链和若干个环构成。

更严谨地，度数不超过 $2$ 的图一定是若干条链 $P_n$ 和若干个环图 $C_n$ 的直和（ $n$ 表示节点数）。

则如果能找到补图 $\overline G$ 的一个哈密顿回路，那么在环上任取 $m$ 条边就能满足要求（题目保证了 $m\le n$ ）

然而判定一张无向图有没有哈密顿回路是 NPC 问题。但是我们可以得到无向图存在哈密顿回路的充分条件。

Dirac 定理：对于一个 $n(n \ge 3)$ 阶无向连通简单图 $G$ ，如果 $\delta(G) \ge \left\lceil\frac{n}{2}\right\rceil$ ，则 $G$ 存在 Hamilton 回路。

考虑题目中的补图 $\overline G$ 的性质。

如果 $G$ 不连通，则除了 $n=1$ 的情况， $\overline G$ 连通。
如果 $G$ 连通，则 $G \cong P_n \lor G \cong C_n$ 。此时除了 $3$ 阶以下的图和 $C_4$ 以外，$\overline G$ 连通。

由于 $\Delta(G) \le 2$ ，所以 $\delta(\overline G)\ge n-3$ 。

因此当 $n\ge 6$ 时，$\overline G$ 为连通图且 $\delta(G) \ge n-3 \ge \left\lceil\frac{n}{2}\right\rceil$ 。根据 Dirac 定理，此时 $\overline G$ 一定有解。

由于 $n<6$ 时情况较少，直接枚举所有情况也能通过。故以下假设 $n \ge 6$ 。

~~接下来就是最鬼畜的时候了~~。

考虑随机枚举图 $\overline{G}$ 。我们直接随机一个排列 $p = \langle x_1,x_2,\cdots,x_n\rangle$

然后把 $p_i$ 与 $p_{(i+1) \bmod n}$ 建边， $\mathcal{O}(n \log n)$ 检验是否合法。

定理：找到解的期望随机次数为 $\mathcal{O}(1)$ 。

证明：不妨设 $G \cong C_n$ 。

我们每次向当前排列尾部增加一个元素 $v$ ，并考虑 $v$ 与当前最后一个元素 $u$ 之间的连边情况。

均摊下来约有 $\frac{n-3}{n-1}$ 的概率满足 $(u,v) \not\in G$ 。则重复 $n-1$ 遍正确的概率为 $\left(\frac{n-3}{n-1}\right)^{n-1}$ 。

因为这里 $\Delta(G)\le 2$ ，固定一对 $u,v$ 是随机的，则 $(u,v) \not\in G$ 的概率为 $\frac{n-3}{n-1}$ （ $u$ 只能连两条边）

当 $n\to +\infty$ 时

$\lim _{n \rightarrow+\infty}\left(\frac{n-3}{n-1}\right)^{n-1} =\lim _{n \rightarrow+\infty}\left(1-\frac{2}{n-1}\right)^{\frac{(n-1)}{2} \times 2} =\mathrm{e}^{-2}$

因此期望次数为 $e^2 = \mathcal{O}(1)$ 。 $\square$

时间复杂度 $\mathcal{O}(N \uparrow n \log n)$ 。其中 $N$ 表示 $n\le 6$ 时的钦定随机次数（当然也可以直接暴力）

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
typedef pair<int,int> pii;
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e5+15))

int n,m,p[N]; bitset<N> b; pii e[N];
bool have(int u,int v)
{ return binary_search<pii*, pii>(e, e + m, minmax(u,v)); }
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    char *_ = new char; mt19937 rd(time(0) + (unsigned int)_); delete _;
    cin >> n >> m;
    for(int i=0,u,v; i<m; i++) { cin >> u >> v; e[i] = minmax(u,v); }
    sort(e, e + m); for(int i=0; i<n; i++) p[i] = i+1;
    for(int T = (n < 6 ? 6666 : INF),cnt; T--; )
    {
        shuffle(p, p + n, rd); p[n] = p[0]; cnt = 0;
        for(int i=0; i<n; i++) cnt += (b[i] = !have(p[i], p[i+1]));
        if(cnt >= m)
        {
            for(int i=0; i<n && m; i++)
            {
                if(!b[i]) continue; m -= b[i];
                cout << p[i] << ' ' << p[i+1] << '\n';
            }
            return 0;
        }
    }
    cout << "-1\n";
    return 0;
}