题解：B3904 [NICA #3] 图造构
P2441M
·
·
题解
## 题意
对于一个 $n$ 个点的无向简单图 $S$，可以通过以下步骤构造出一个新图 $S'$：
- 初始时 $S'$ 中只有 $n$ 个孤点。
- 选择 $S$ 中不同的两个度数相同的点 $u,v$，在 $S'$ 中连接 $u,v$，在 $S$ 中删去 $u$ 极其出边。
- 当 $S$ 中只剩下一个点时停止操作。
现在给定两张 $n$ 个点构成的无向简单图 $S,T$，边数分别为 $m_S,m_T$。给出一种方案，使得 $S$ 在 $k(1\leq k\leq 3)$ 次构造后变成 $T$。数据保证有解，$2\leq n\leq 10^5$，$1\leq m_S,m_T\leq 2\times 10^5$。
## 题解
构造好题。
不难看出构造得到的简单图一定是一棵树，因为操作恰好会进行 $n-1$ 次，且每个点都有连边。我们考虑先对 $S$ 随便做一次构造得到一棵树 $P$，然后尝试通过 $2$ 次构造得到树 $T$。
对于一棵至少有 $2$ 个点的树 $P$，显然其中至少包含 $2$ 个叶子节点。我们不妨钦定某个叶子节点 $p$ 保留不动，然后不断在 $P$ 中找到异于 $p$ 的叶子节点 $q$，执行操作 $(q,p)$。这样我们就得到了一棵以 $p$ 为根的菊花图。
在菊花图中，任意两个异于 $p$ 的点 $a,b$ 都是可以操作的，如果我们保证 $p$ 在 $T$ 中是一个叶子节点，那么我们就可以执行和刚才类似的操作：把 $p$ 视作 $T$ 的根，不断找到 $T$ 中异于 $p$ 的叶子节点 $q$，执行操作 $(q,fa_q)$。由于保证了 $p$ 的度数为 $1$，所以最后有且仅有 $1$ 次操作形如 $(q,p)$，是合法的。
这样我们就可以通过恰好 $3$ 次构造从 $S$ 变成 $T$ 了。
首先在最开始，我们在 $T$ 中找到任意一个度数为 $1$ 的点 $p$。
对于后面两次构造，我们可以用类似拓扑排序的方法实现。在队列中维护所有度数为 $1$ 的点 $u(u\neq p)$，每次取出一个点时遍历出边，将新的度数为 $1$ 的点加入队列中即可。时间复杂度是 $\mathcal{O}(n)$ 的。
难点在于第一次构造。一种实现方法是，对于每一种度数 $d$，开一个 `set` 维护其对应点集，然后再用一个 `set` 维护 $(d,c)$ 二元组，表示当前度数为 $d$ 的点有 $c$ 个，每次从这个 `set` 中取出 $c$ 最大的二元组更新。时间复杂度是 $\mathcal{O}((n+m_S)\log{n})$ 的。
能不能再给力一点啊？
我们仍然尝试用队列维护这个过程。对于每一种度数 $d$，开一个 `vector` 维护对应点集，把所有点集大小 $\geq 2$ 的度数加入队列中。每次取出一个度数 $d$ 时，从对应 `vector` 中取出尾部的两个点 $x,y$。遍历 $x$ 的出边时，一些点的度数会被更改，这时不用从 `vector` 中删除，我们只需要在从 `vector` 的尾部取点时惰性删除那些度数不等于 $d$ 的点即可。时间复杂度均摊下来是优秀的 $\mathcal{O}(n+m_S)$。
注意这部分构造的一些细节：
- 题目不保证图连通，要考虑度数为 $0$ 的点。
- 每次取出两个点 $x,y$ 时，**若其中有一个点是 $p$，则需要保证被删除的点是 $p$**，这样可以确保在 $P$ 中 $p$ 的度数为 $1$。
这样我们就 $\mathcal{O}(n+m_S)$ 地解决了本题。
## 代码
```cpp
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
#define lowbit(x) ((x) & -(x))
#define chk_min(x, v) (x) = min((x), (v))
#define chk_max(x, v) (x) = max((x), (v))
typedef long long ll;
typedef pair<int, int> pii;
const int N = 1e5 + 5, M = 2e5 + 5;
int n, ms, mt, rt;
bool del[N];
queue<int> q;
vector<int> p[N];
struct AdjList {
int tot, head[N], deg[N], nxt[M << 1], to[M << 1];
inline void init() { tot = 0, fill(head + 1, head + n + 1, -1); }
inline void ins(int x, int y) { ++deg[to[++tot] = y], nxt[tot] = head[x], head[x] = tot; }
} S, T, P;
int main() {
ios::sync_with_stdio(0), cin.tie(0);
cin >> n, S.init(), T.init(), P.init();
cin >> ms;
for (int i = 1, u, v; i <= ms; ++i) cin >> u >> v, S.ins(u, v), S.ins(v, u);
cin >> mt;
for (int i = 1, u, v; i <= mt; ++i) cin >> u >> v, T.ins(u, v), T.ins(v, u);
cout << "3\n";
for (int i = 1; i <= n; ++i) if (T.deg[i] == 1) { rt = i; break; }
for (int i = 1; i <= n; ++i) p[S.deg[i]].push_back(i);
for (int i = 0; i < n; ++i) if (p[i].size() >= 2) q.push(i);
while (!q.empty()) {
int d = q.front(); q.pop();
while (!p[d].empty() && S.deg[p[d].back()] != d) p[d].pop_back();
if (p[d].empty()) continue;
int x = p[d].back(); p[d].pop_back();
while (!p[d].empty() && S.deg[p[d].back()] != d) p[d].pop_back();
if (p[d].empty()) { p[d].push_back(x); continue; }
int y = p[d].back(); p[d].push_back(x);
if (y == rt) swap(x, y);
P.ins(x, y), P.ins(y, x);
cout << x << ' ' << y << '\n';
del[x] = 1, S.deg[x] = -1;
for (int i = S.head[x]; ~i; i = S.nxt[i]) {
int y = S.to[i];
if (del[y]) continue;
p[--S.deg[y]].push_back(y);
if (p[S.deg[y]].size() >= 2) q.push(S.deg[y]);
}
if (p[d].size() >= 2) q.push(d);
}
fill(del + 1, del + n + 1, 0);
for (int i = 1; i <= n; ++i) if (i != rt && P.deg[i] == 1) q.push(i), del[i] = 1;
while (!q.empty()) {
int x = q.front(); q.pop();
cout << x << ' ' << rt << '\n';
for (int i = P.head[x]; ~i; i = P.nxt[i]) {
int y = P.to[i];
if (del[y]) continue;
if (--P.deg[y] == 1) q.push(y), del[y] = 1;
}
}
fill(del + 1, del + n + 1, 0);
for (int i = 1; i <= n; ++i) if (i != rt && T.deg[i] == 1) q.push(i), del[i] = 1;
while (!q.empty()) {
int x = q.front(); q.pop();
for (int i = T.head[x]; ~i; i = T.nxt[i]) {
int y = T.to[i];
if (del[y]) continue;
cout << x << ' ' << y << '\n';
if (--T.deg[y] == 1) q.push(y), del[y] = 1;
}
}
return 0;
}
```