题解：CF1656I Neighbour Ordering

_xixi · 2026-11-06 16:58:51 · 题解

CF1656I Neighbour Ordering

给定 n 个点 m 条边的简单连通无向图，给每个点定一个邻居排序，使对于图上任意简单环都满足以下两种情况至少一种成立：

对于环上任意一个点，都有在其邻居排序中前驱小于后继。

对于环上任意一个点，都有在其邻居排序中前驱大于后继。

构造方案或判断无解。

显然对于每个点双是独立的，因为没有跨点双的简单环。先特判只有一条边的点双。

考虑找一些必要条件。发现如果两个点之间存在 \ge 3 条点不交且是不一条边的链，那么一定无解。

证明：

不妨设图形如 u\to A,B,C\to v，假设 A,B,C 是一个点。因为有环 u\to A\to v\to B\to u，所以在 A 时 u,v 顺序与在 B 时不同。同理可得 A,B,C 时的 u,v 顺序都不同，显然矛盾。

对于 A,B,C 不是一个点可以直接任选其中一个点。

这说明这张图上一定有哈密顿环。证明：取出点双中的最长环，如果其不是哈密顿环，那么一定存在一条在这个外的路径连接这个环上的不同点 x,y，如果 x,y 相邻就可以拼成一个新环，与最长性矛盾，否则与上面条件矛盾。取出这个哈密顿环，观察样例发现如果环上存在交叉边就无解，下面给出证明。

证明：

不妨设图形如这个样子，且对于整个最大的环，在 2 时 1<3。对于 2,3,4,5 这个环，在 5 时 4<2，对于 2,1,6,5 这个环，在 2 时 1<5。

对于 1,2,5,4 这个环，就矛盾了。所以一定无解。

所以现在的必要条件为：

每个点双必须要哈密顿环。
这个哈密顿环上没有交叉边。

可以说明这样是充分的。具体的构造方法：先给哈密顿环随便定个向，对于每个点 u，把邻居 v 按照 u 走到 v 的距离从小到大排序，得到的就是合法邻居排序。

证明：

因为哈密顿环边不交，所以图上任意一个环都是哈密顿环去掉一些部分得到。而对于环上的点 u 的两个邻居，他们的大小关系取决与从 u 开始按定向后的环走先碰到谁，容易手玩发现一定合法。

现在还有一个问题是判断一个图是否有哈密顿环是 NP-Hard 的，但是这个哈密顿环还有满足没有交叉边这一性质。考虑利用这一性质，容易发现这样的图一定存在 2 度点，每次找到一个二度点并删去，然后在这个点连接的两个点之间连边（如果原本有就不连），那么就是一个子问题，边界为只剩下两个点的情况。

然后构造环只需把删除点的顺序反过来加入即可。容易发现如果遇到剩下 >2 个点或者在环上 x,y 之间插入一个点 u 时 x,y 已经不相邻，那么一定不合法（通过手玩可以感受到）。否则图一定满足条件，注意此时可能会在最后剩下的两个点出现边界问题，所以在构造出环后判断这两个点与相邻点是否有边。

找到环之后就按照上面的构造方法构造，总时间 O(n\log n)。

有个细节是怎么找点双对应的边，显然这些边就是所有满足，点双中除在 dfs 树上最浅点外的点连向深度更小的边。

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define pii pair<int, int>
using namespace std;

const int maxn = 3e5 + 5;
int n, m, dfn[maxn], low[maxn], tot, sc, st[maxn], tp, deg[maxn], l[maxn], r[maxn];
int pos[maxn], tt;
bool f;
vector<int> ans[maxn];
vector<int> E[maxn], E1[maxn], t1[maxn], E2[maxn];
vector<pii> t2[maxn];
bool vis[maxn];
struct node{
    int u, x, y;
};

void init(){
    for(int i = 1; i <= sc; i++){
        t1[i].clear(); t2[i].clear();
    }
    tot = sc = tp = 0;
    for(int i = 1; i <= n; i++){
        dfn[i] = low[i] = 0;
        E[i].clear();
        E1[i].clear();
        ans[i].clear();
    }
}

void tarjan(int u, int las){
    st[++tp] = u;
    dfn[u] = low[u] = ++tot;
    for(int v : E[u]){
        if(!dfn[v]){
            E1[v].pb(u);
            tarjan(v, u);
            low[u] = min(low[u], low[v]);
            if(low[v] >= dfn[u]){
                sc++;
                t1[sc].pb(u);
                while(1){
                    int x = st[tp--];
                    t1[sc].pb(x);
                    for(int y : E1[x]) t2[sc].pb({x, y});
                    if(x == v) break;
                }
            }
        }else if(v ^ las){
            low[u] = min(low[u], dfn[v]);
            if(dfn[u] > dfn[v]) E1[u].pb(v);
        }
    }
}

void solve(int id){
    vector<pii> &e = t2[id];
    vector<int> &V = t1[id];
    if(V.size() == 2){
        ans[V[0]].pb(V[1]);
        ans[V[1]].pb(V[0]);
        return ;
    }
    queue<int> q;
    unordered_map<ll, int> mp;
    for(int i : V) E2[i].clear(), deg[i] = vis[i] = 0;
    for(auto [u, v] : e){
        E2[u].pb(v), E2[v].pb(u), deg[u]++, deg[v]++;
        mp[1ll * u * maxn + v] = mp[1ll * v * maxn + u] = 1;
    }
    vector<node> tmp;
    for(int i : V) if(deg[i] == 2) q.push(i);
    while(!q.empty()){
        int u = q.front(); q.pop();
        if(vis[u] || deg[u] != 2) continue;
        vis[u] = 1;
        int x = -1, y = -1;
        for(int z : E2[u]) if(!vis[z]){
            if(x == -1) x = z;
            else y = z;
        }
        tmp.pb({u, x, y});
        deg[x]--; deg[y]--;
        if(!mp[1ll * x * maxn + y]){
            mp[1ll * x * maxn + y] = mp[1ll * y * maxn + x] = 1;
            E2[x].pb(y); E2[y].pb(x);
            deg[x]++; deg[y]++;
        }
        q.push(x);
        q.push(y);
    }
    vector<int> t;
    for(int i : V) if(!vis[i]) t.pb(i);
    if(t.size() != 2){
        f = 0;
        return ;
    }
    for(int i : V) l[i] = r[i] = 0;
    reverse(tmp.begin(), tmp.end());
    r[t[0]] = t[1]; l[t[1]] = t[0];
    int end = t[1];
    for(auto [u, x, y] : tmp){
        if(r[y] == x) swap(x, y);
        if(r[x] == y){
            r[x] = u; l[u] = x;
            r[u] = y; l[y] = u;
            continue;
        }
        if(y == t[0]) swap(x, y);
        if(x == t[0] && y == end){
            r[y] = u; l[y] = 0;
            end = u;
            continue;
        }
        f = 0;
        return ;
    }
    bool fl = 0;
    for(auto [p, q] : e){
        if(t[0] == p && end == q) fl = 1;
        if(end == p && t[0] == q) fl = 1;
    }
    if(!fl){
        f = 0;
        return ;
    }
    tt = 0;
    int x = t[0];
    while(x){
        pos[x] = ++tt;
        end = x;
        x = r[x];
    }
    for(int i : V) E2[i].clear();
    for(auto [u, v] : e) E2[u].pb(v), E2[v].pb(u);
    for(int i : V){
        sort(E2[i].begin(), E2[i].end(), [=](int x, int y){
            return (pos[i] - pos[x] + tt) % tt < (pos[i] - pos[y] + tt) % tt;
        });
        for(int j : E2[i]) ans[i].pb(j);
    }
}

void solve(){
    init();
    cin >> n >> m;
    for(int i = 1; i <= m; i++){
        int u, v; cin >> u >> v;
        u++; v++;
        E[u].pb(v); E[v].pb(u);
    }
    tarjan(1, 0);
    f = 1;
    for(int i = 1; i <= sc; i++) solve(i);
    if(!f){
        cout << "NO\n";
        return ;
    }
    cout << "YES\n";
    for(int i = 1; i <= n; i++, cout << '\n') for(int j : ans[i]) cout << j - 1 << ' ';
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int t; cin >> t; while(t--) solve();

    return 0;
}