题解 - CCPC Final 2022 B Disjoint Set Union

好难的刻画！

题意简述

给一个合法的并查集数组，构造一组方案使得它变为给定的目标并查集数组，可用的操作包括路径压缩的 find(x) 和合并联通块 unite(x, y)。多组数据 $n\le 10^3, \sum n\le 5\times 10^6$。

等价转换

我们假设初始数组为 $a_i$，目标数组为 $b_i$。

实际上是什么意思？追踪一下 $a_p$ 的变化，发现 $b_p$ 可能是这两种 case 之一：

• 关于 $p$ 最后一次操作实现了 find(p)，此时 $p$ 所在联通分量的根是 $b_p$；
• 关于 $p$ 最后一次操作是 unite(p, b[p])，这之前 $p, b_p$ 分别是各自联通分量的根。

最后一次操作的限制就是这之后，$p$ 子树内不再有任何操作，除了当 $p$ 深度（指和根的距离）为 $1$ 时它的儿子的 find() 操作，这种操作并不会改变其他结构。

其实可以稍微化简一下，整个过程应该有一些 unite() 来划分阶段。而每个阶段对于每个 $p$，只要 $a_p\neq b_p$，深度 $\ge 2$ 都一定要执行一次 find(p)。

那么 find() 的逻辑就比较清楚了，但是我们怎么 unite()？

处理限制

我们知道初始时满足 $a_p\neq b_p$ 的 $p$ 一定会进行 find(p)。那么这一轮过后这个并查集形如菊花森林。考虑菊花根和非菊花根的限制。

• 菊花根的限制：一定是先确定 $p$，然后把 $p$ 连成 $b_p$ 的儿子，之后可能确定 $b_p$。如果连之前 $p$ 和 $b_p$ 在不同联通分量，则要 unite(p, b[p])。
• 非菊花根的限制：假设已经进行完初始必需的操作，只讨论 $a_p\neq b_p$ 的情况。在某个时刻 $b_p$ 是 $p$ 的祖先（二级父亲，联通分量的根），然后进行一次 find(p) 做到转移。所以一定是先确定 $a_p$，然后可能确定 $b_p$。

归纳一下就是，假设已经进行完初始必需的操作，在所有 $a_p\neq b_p$ 的情况，$a_p$ 要先于 $b_p$ 完成最后的操作。

这个形式就可以建图，做拓扑排序，如果有一个合法的拓扑序就构造方案，假设拓扑序的当前位是 $p$，它必须有 $a_p=p\land a_p\neq b_p$（否则无法进行操作）。我们找到它应该 unite() 的目标，unite() 后完成它所有儿子的 find()。所谓 unite() 的目标，就是接下来最早出现的点，满足 $p$ 和 $p$ 的儿子们可能以它为 $b$ 值（如果更早，不优；如果更晚，会漏）。如果这个过程不可以正确进行，或者最后 $a\neq b$，都是无解。

代码

#include <bits/stdc++.h>
using namespace std;

const int MXN = 1005;
int T, N, fa[MXN], tgt[MXN];
int deg[MXN], que[MXN], qh, qt, ord[MXN];
vector<tuple<int, int, int>> ans;
vector<int> lim[MXN];

int _find(int x) { return fa[x] ^ x ? fa[x] = _find(fa[x]) : x; }
inline int find(int x) {
  if (fa[fa[x]] ^ fa[x]) ans.emplace_back(1, x);
  return _find(x);
}
inline void merge(int x, int y) {
  ans.emplace_back(2, x, y);
  fa[_find(x)] = _find(y);
}
bool work() {
  cin >> N;
  for (int i(0); i != N; ++i) cin >> fa[i], --fa[i];
  for (int i(0); i != N; ++i) cin >> tgt[i], --tgt[i];
  ans.clear();
  for (int i(0); i != N; ++i) {
    int p(i);
    for (int c(N); tgt[p] ^ p && c--;) p = tgt[p];
    if (tgt[p] ^ p) return false;
  }
  for (int i(0); i != N; ++i) deg[i] = 0, lim[i].clear();
  for (int i(0); i != N; ++i) {
    if (fa[i] ^ tgt[i]) {
      find(i);
      if (fa[i] ^ tgt[i]) lim[fa[i]].push_back(tgt[i]), ++deg[tgt[i]];
    }
  }
  qh = qt = 0;
  for (int i(0); i != N; ++i) if (!deg[i]) que[qt++] = i;
  while (qh != qt) {
    int c(que[qh]);
    ord[c] = qh++;
    for (int n : lim[c]) if (!--deg[n]) que[qt++] = n;
  }
  if (qt != N) return false;
  for (int i(0); i != N; ++i) {
    int p(que[i]);
    if (fa[p] == tgt[p] || fa[p] ^ p) continue;
    int f(-1);
    for (int j(0); j != N; ++j)
      if (fa[j] == p && fa[j] ^ tgt[j] && (f == -1 || ord[tgt[j]] < ord[f]))
        f = tgt[j];
    if (~f) {
      merge(p, f);
      for (int j(0); j != N; ++j)
        if (fa[j] == p && fa[j] ^ tgt[j]) find(j);
    }
  }
  for (int i(0); i != N; ++i)
    if (fa[i] != tgt[i]) return false;
  cout << "YES\n" << ans.size() << '\n';
  for (auto [o, x, y] : ans)
    if (o == 1) cout << "1 " << x + 1 << '\n';
    else cout << "2 " << x + 1 << ' ' << y + 1 << '\n';
  return true;
}

int main() {
  for (cin >> T; T--;) if (!work()) cout << "NO\n";
  return 0;
}