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;
}