题解：CF1477D Nezzar and Hidden Permutations

Phartial · 2025-05-01 20:27:53 · 题解

注意到，不管我们如何定向这张无向图，对于所有度数为 n-1 的点，其他点要么只能在它的前面，要么只能在它的后面，所以所有度数为 n-1 的点在任意拓扑序里的出现位置是固定的。不妨钦定它们总是出现在拓扑序的最开头。

那么剩下的 n' 个点度数不超过 n'-2，也就是在补图中所有点的度数至少为 1。

注意到，如果补图中有一个菊花，那么这个菊花里的所有点在拓扑序中的出现位置就都可以改变：拓扑序中可以先出现中心点再出现其他点，也可以先出现其他点再出现中心点。这启示我们将所有点划分到若干个不交的菊花中。

对补图里的每个连通块，我们找出它的一棵生成树，接下来对这棵生成树进行 bfs：

• 如果当前点的父亲是某个菊花的中心：则可以直接将当前点划分到父亲所在的菊花中；
• 如果当前点不是叶子：直接将其当作菊花的中心即可；
• 如果当前点是叶子：
  • 则如果其父亲所在的菊花大小至少为 3，就将其父亲从它所在的菊花中取出来并设置为新的菊花中心，然后将当前点划分到父亲所在的菊花中即可；
  • 否则如果其父亲所在的菊花大小为 2，我们就将菊花中心移动到其父亲，再将当前点划分到父亲所在的菊花中。

显然这一过程可以将整棵生成树划分为若干个不交的菊花，任意地为菊花之间确定一个拓扑序，并输出方案即可。

#include <iostream>
#include <set>
#include <vector>

using namespace std;

const int kN = 5e5 + 1;

int tt, n, m, l[2][kN], c, f[kN], d[kN], dc, r[kN], q[kN], h, t;
bool v[kN];
vector<int> g[kN];
set<int> e[kN], s, w[kN];

void D(int x) {
  v[x] = 1;
  for (int i : s) {
    if (!e[x].count(i)) {
      g[x].push_back(i), f[i] = x;
    }
  }
  for (int i : g[x]) {
    s.erase(i);
  }
  for (int i : g[x]) {
    D(i);
  }
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  for (cin >> tt; tt--;) {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
      e[i].clear(), v[i] = f[i] = d[i] = r[i] = 0, g[i].clear(), w[i].clear();
    }
    s.clear(), c = dc = 0;
    for (int i = 1, x, y; i <= m; ++i) {
      cin >> x >> y;
      e[x].insert(y), e[y].insert(x);
    }
    for (int i = 1; i <= n; ++i) {
      if (e[i].size() == n - 1) {
        l[0][i] = l[1][i] = ++c;
        v[i] = 1;
      } else {
        s.insert(i);
      }
    }
    for (int i = 1; i <= n; ++i) {
      if (!v[i]) {
        s.erase(i);
        D(i);
        q[h = t = 1] = i;
        for (; h <= t; ++h) {
          for (int j : g[q[h]]) {
            q[++t] = j;
          }
          int x = q[h];
          if (f[x] && f[x] == r[d[f[x]]]) {
            w[d[x] = d[f[x]]].insert(x);
          } else if (!g[x].empty()) {
            w[d[x] = ++dc].insert(x), r[dc] = x;
          } else if (w[d[f[x]]].size() == 2) {
            r[d[f[x]]] = f[x];
            w[d[x] = d[f[x]]].insert(x);
          } else {
            w[d[f[x]]].erase(f[x]);
            w[d[x] = d[f[x]] = ++dc].insert(x), w[dc].insert(f[x]), r[dc] = f[x];
          }
        }
      }
    }
    for (int i = 1; i <= dc; ++i) {
      l[0][r[i]] = ++c;
      for (int j : w[i]) {
        if (j != r[i]) {
          l[1][j] = c;
          l[0][j] = ++c;
        }
      }
      l[1][r[i]] = c;
    }
    for (int o : {0, 1}) {
      for (int i = 1; i <= n; ++i) {
        cout << l[o][i] << ' ';
      }
      cout << '\n';
    }
  }
  return 0;
}