「codeforces - 1361C」Johnny and Megan's Necklace

link。

考虑枚举答案判断可行性，设我们枚举的答案是 $k$，则可行的条件是 $\forall (u, v) \in \mathbf E$，$a_u \& (2^k-1) = a_v \& (2^k-1)$。问题在于复杂度，如果我们直接把等价点内部连边跑匹配的话边的数量级是 $O(n^2)$ 的，这里有一个优化的技巧：把一个等价点集合看作一个独立点，所有集合内点向该独立点连边，边数便消减成为了 $O(n)$。

考虑此时的条件，即是整张图构成一个欧拉图，考虑一笔画。

int n, a[1<<20], b[1<<20], cnt[1<<22], beg[1<<22], nxt[1<<22], to[1<<22], ent, vis[1<<22];
void ae(int x, int y) {
    to[++ent] = y, nxt[ent] = beg[x], beg[x] = ent;
    to[++ent] = x, nxt[ent] = beg[y], beg[y] = ent;
}
int S[1<<22], tp;
void push_stack(int x) {
    for (int& i=beg[x]; i; i=nxt[i]) if (!vis[i]) {
        int v = to[i];
        vis[i] = vis[i^1] = 1, assert(to[i] > 0), push_stack(to[i]), S[++tp] = v;
    }
}
bool construct(int bts) {
    int U = 1<<bts; U--;
    memset(cnt, 0, sizeof cnt);
    rep(i,1,n+1) cnt[a[i]&U]++;
    rep(i,1,n+1) cnt[b[i]&U]++;
    bool RS = count_if(cnt, cnt+U+1, [&](int x) -> bool { return x%2==1; });
    if (RS) return 0;
    memset(beg, 0, sizeof beg);
    memset(vis, 0, sizeof vis);
    ent = 1;
    rep(i,1,n+1) ae(i, (a[i]&U)+n+1);
    rep(i,1,n+1) ae(i, (b[i]&U)+n+1);
    tp = 0;
    push_stack(1);
    int CT = count_if(S+1, S+tp+1, [&](int x) -> bool { return x <= n; });
    if (CT != n) return 0;
    cout << bts << "\n";
    for (int p=1,x; p<=tp; ++p) {
        if ((x = S[p]) <= n) {
            int s = S[p+1]-n-1;
            if ((a[x]&U) == s) cout << x*2 << " " << x*2-1 << " ";
            else cout << x*2-1 << " " << x*2 << " ";
        }
    }
    cout << "\n";
    exit(0);
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    rep(i,1,n+1) cin >> a[i] >> b[i];
    drep(i,21,1) construct(i);
    cout << "0\n";
    rep(i,1,n*2+1) cout << i << " \n"[i == n*2];
}