题解 - 省选联考 2025 图排列

前言

喜欢这个题，推理链长而完整，考察代码实现但不严重，没什么很一拍脑袋的步骤，场上差最后一步而只有 52 分是一款我的问题。

简述题意

给一简单无向图，求字典序最小的排列 $p$，满足将每条边 $(u_i,v_i)$ 视作区间 $[\min(p_{u_i},p_{v_i}), \max(p_{u_i},p_{v_i}))$ 后，区间要么相离，要么一者包含另一者。点数 $n\le 10^5$，边数 $m\le 2n$，保证有解。

性质 AC：图为一棵树

手玩，每个点一定是形如：有些子树在它左边、有些子树在它右边，子树之间两两不交，而这个结构可以向子树递归。那只关心每个子树答案的首位，在该点处排序即可。考虑到随便选根，根可能被某条边代表的区间包含，所以以编号最小的点作为根，它必然在答案的首位。

性质 C：多个联通块的合并

手玩，不同联通块之间要么相互包含，要么相离。根据字典序最小的贪心想法，考虑对每个联通块求出答案，按首位排序，依次输出。如果发现下一个联通块的首位要小于即将要输出的数，就跳到下一个联通块。

环的情况

手玩，发现环上的点出现的顺序必然是：环的某个顺序的某个循环表示。建立圆方树，圆点遵循上面的规则，方点就是把儿子按环上的顺序依次排序，选取正序和逆序中更优者。

点双的性质

1. 此点双不含同胚于 $K_4$ 的子图。$K_4$ 表示大小为 $4$ 的完全图。也就是说此点双是广义串并联图。手玩可证。
2. 此点双不含同胚于以下结构的子图（$K_{2,3}$）：

考虑三个环 1 2 5 3、1 2 5 4、1 3 5 4 都要符合上述对于环的分析，手玩发现不可能。这里同时证明了点双哈密顿环的存在性。

总结一下：这个点双形如一个圆，上面有一些不相交的弦。这里哈密顿环的唯一性也显然（删去任意一条环边原图将不再是点双，非环边则反之，暴力方法可以获得 72 分）。把哈密顿环找到，按环的方法做即可。

广义串并联图方法

由广义串并联图的套路，以及这是针对点双，考虑在点双上面不断地缩二度点和叠合重边来找到哈密顿环。

简单地说，你发现缩二度点的过程拉成重构树，环上的点就已经排好序。所以一开始认为所有的边都有效，叠合重边的时候把长度为 1 的边删去即可。

总复杂度 $O(n\log n)$。

代码

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

const int MXN = 100005;
const int MXV = MXN * 2;
int T, N, M, V;
int dfn[MXN], low[MXN], did;
int cid, stk[MXN], top;
int que[MXN], qh, qt;
bool instk[MXN];
vector<int> to[MXN], comps[MXN], nto[MXV];
vector<pair<int, int>> segs[MXV];
set<int> rese[MXN], vire[MXN];

inline int read() {
  int x(0), c(getchar());
  while (c < '0' || c > '9') c = getchar();
  while (c >= '0' && c <= '9') x = x * 10 + (c - '0'), c = getchar();
  return x;
}
inline void write(int x) {
  assert(x);
  static char buf[11];
  int d(0);
  while (x) buf[d++] = x % 10 + '0', x /= 10;
  while (d) putchar(buf[--d]);
}

void build_scc(int p, int q, int s) {
  nto[p].push_back(s);
  int otop(top);
  stk[++otop] = p;
  while (true) {
    int c(stk[top--]);
    instk[c] = false;
    for (int i : to[c]) {
      if (instk[i] && dfn[i] >= dfn[p]) {
        rese[c].insert(i), rese[i].insert(c);
        vire[c].insert(i), vire[i].insert(c);
      }
    }
    if (c == q) break;
  }
  qh = qt = 0;
  for (int i(top + 1); i <= otop; ++i) {
    int c(stk[i]);
    if (rese[c].size() == 2) que[qt++] = c;
  }
  while (qh != qt) {
    int c(que[qh++]);
    if (rese[c].size() != 2) break;
    int x(*rese[c].begin());
    int y(*next(rese[c].begin()));
    rese[x].erase(c), rese[y].erase(c);
    if (rese[x].find(y) != rese[x].end()) {
      vire[x].erase(y), vire[y].erase(x);
      if (rese[x].size() == 2) que[qt++] = x;
      if (rese[y].size() == 2) que[qt++] = y;
    } else {
      rese[x].insert(y), rese[y].insert(x);
    }
  }
  int x(que[qh - 1]), y(que[qh]);
  if (vire[x].size() == 1) vire[x].insert(y), vire[y].insert(x);
  for (int c(*vire[p].begin()), l(p);;) {
    nto[s].push_back(c);
    int n(*vire[c].begin() + *next(vire[c].begin()) - l);
    if (n == p) break;
    l = c, c = n;
  }
  for (int i(top + 1); i <= otop; ++i) {
    int c(stk[i]);
    rese[c].clear(), vire[c].clear();
  }
}
void build(int p, int f) {
  low[p] = dfn[p] = did++;
  instk[p] = true, stk[++top] = p;
  for (int q : to[p]) {
    if (q == f) continue;
    if (dfn[q] == -1) {
      build(q, p);
      low[p] = min(low[p], low[q]);
      if (low[q] == dfn[q]) {
        nto[p].push_back(q);
        instk[q] = false;
        --top;
      } else if (low[q] == dfn[p]) {
        build_scc(p, q, V++);
      }
    } else {
      low[p] = min(low[p], dfn[q]);
    }
  }
}

void calc(int p) {
  segs[p].clear();
  if (p < N) segs[p].emplace_back(p, p);
  for (int q : nto[p]) {
    calc(q);
    segs[p].emplace_back(segs[q][0].first, q);
  }
  if (p < N)
    sort(segs[p].begin(), segs[p].end());
  else if (segs[p].back().first < segs[p][0].first)
    reverse(segs[p].begin(), segs[p].end());
}
void generate(int p, int ci) {
  for (auto [fir, q] : segs[p]) {
    if (q == p) comps[ci].push_back(p);
    else generate(q, ci);
  }
}
void output(int layer) {
  for (int i : comps[layer]) {
    while (top != cid && comps[top][0] < i) output(top++);
    write(i + 1), putchar(' ');
  }
}

int main() {
  for (read(), T = read(); T--;) {
    N = read(), M = read();
    for (int i(0); i != N; ++i) to[i].clear();
    for (int x(0), y(0); M--;) {
      x = read() - 1, y = read() - 1;
      to[x].push_back(y), to[y].push_back(x);
    }
    did = 0;
    fill(dfn, dfn + N, -1);
    for (int i(0); i != N + N; ++i) {
      segs[i].clear();
      nto[i].clear();
    }
    V = N;
    cid = 0;
    for (int i(0); i != N; ++i) {
      if (~dfn[i]) continue;
      top = -1, build(i, -1);
      calc(i);
      comps[cid].clear(), generate(i, cid++);
    }
    top = 0;
    while (top != cid) output(top++);
    putchar('\n');
    cout << flush;
  }
  return 0;
}