题解：P14464 海底列車（collapse）

· · 题解

前言

因为没有题解的代码可以搬运借鉴，我这样的铸币对着思慕代码调了半天，所以考虑贴个代码。

做法

注意到操作前后点的度数不会改变，大胆猜测有解当且仅当 S 与 T 的点染色后相同颜色的点度数同构。然后构造答案。
首先根据同构结果我们可以得到一个 S 与 T 之间一一对应的映射关系。我们直接不考虑所有的一度点之间的对应，只要求非一度点按照映射关系进行同构。（因为如果所有非一度点的形状和度数都同构，那么剩下还没有填的位置填的肯定是一度点，两树一定同构）
首先钦定一个根，然后考虑将所有的儿子换为同构的儿子。假设当前点为 x，当前儿子为 u，目标儿子为 v。

完成。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 5e3+7;
int n;
struct gra{//链式前项星，其中deg是度数，col是染色结果 
    int m;
    int head[N];
    int nxt[N<<1], to[N<<1];
    int deg[N];
    short col[N];
    void add(int x, int y){
        deg[x]++;
        to[++m] = y;
        nxt[m] = head[x];
        head[x] = m;
    }
}s, t;
bool cmp(int x, int y){//两种比较函数本质相同 
    if(s.deg[x] == s.deg[y]) return s.col[x] > s.col[y];
    return s.deg[x] > s.deg[y];
}
bool cmp2(int x, int y){
    if(t.deg[x] == t.deg[y]) return t.col[x] > t.col[y];
    return t.deg[x] > t.deg[y];
}
int ano[N<<1];//指向s中第i条边的反边 
int sors[N], srot[N];//分别是s的重构后顺序,t的重构后顺序 
int oth[N];//在dfs时用作t的点的映射，输出答案时用作s的点的映射 
int k;//记录答案长 
struct uct{//答案 
    int x, y;
}ans[N<<1];
int f(int x, int co, int root){//当root作为根时，x指向父亲的边（co是来时点所以不考虑）
    //！！！注意此函数返回的是边！ 
    if(x == root) return -1;
    for(int i = s.head[x]; i; i = s.nxt[i]){
        int y = s.to[i];
        if(y == co) continue;
        if(f(y, x, root)) return i;
    }
    return 0;
}
int opt;//我饭堂写的，实际可以证明恒等于0 
void swp(int x, int y){//交换两个点 
    ans[++k] = (uct){x, y};
    assert((s.col[x]^s.col[y]) == 0);
    int a = f(x, 0, y), c = f(y, 0, x);
    int b = ano[a], d = ano[c];
    swap(s.to[a], s.to[c]);
    swap(s.to[b], s.to[d]);
    swap(ano[a], ano[c]);
    swap(ano[b], ano[d]);
}
int ason(int x, int fx){//返回除fx之外,x的一个儿子，返回值是边的编号
    if(s.to[s.head[x]] == fx) return s.nxt[s.head[x]];
    else return s.head[x];
}
struct gra* er;
void dfs0(int x, int fx){//染色 
    (*er).col[x] = (*er).col[fx]^1;
    for(int i = (*er).head[x]; i; i = (*er).nxt[i]){
        int y = (*er).to[i];
        if(y == fx) continue;
        else dfs0(y, x);
    }
}
bool check(){//检查是否同构 
    sort(srot+1, srot+n+1, cmp2);
    opt = s.col[sors[1]]^t.col[srot[1]];
    for(int i = 1; i <= n; i++){
        if(s.deg[sors[i]] != t.deg[srot[i]] || (s.col[sors[i]]^t.col[srot[i]]) != opt) return false;
        oth[srot[i]] = sors[i];
    }
    return true;
}
void dfs2(int x, int fx, int y, int fy){//x与y已经匹配，正在匹配所有儿子 
    assert(fx != 0 && fy != 0);
    int i = s.head[x], j = t.head[y];
    if(s.to[i] == fx) i = s.nxt[i];
    if(t.to[j] == fy) j = t.nxt[j];
    for(; i; ){//遍历时跳过父亲 
        int p = s.to[i], q = oth[t.to[j]];
        assert(s.col[p] == s.col[q]); 
        if(f(p, x, q) != 0){//在一棵子树上 
            if(s.deg[q] != 1 && p != q) swp(s.to[ason(q, s.to[f(q, 0, x)])], x);
        }else swp(p, q);//不在一棵子树上 
        if(s.to[i] == oth[t.to[j]]) dfs2(s.to[i], x, t.to[j], y);//如果是叶子就不要处理，顺其自然 
        do{ i = s.nxt[i];
        }while(s.to[i] == fx);
        do{ j = t.nxt[j];
        }while(t.to[j] == fy);
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0); 
    freopen("collapse.in", "r", stdin);
    freopen("collapse.out", "w", stdout);
    cin >> n;
    for(int i = 1; i < n; i++){
        int x, y;
        cin >> x >> y;
        s.add(x, y);
        s.add(y, x);
    }
    for(int i = 1; i < n; i++){
        int x, y;
        cin >> x >> y;
        t.add(x, y);
        t.add(y, x);
    }
    if(n <= 3){//事实证明数据过水，这个输出格式是之前写的所以是错的
        //n<=3时可能会出现诸如只有叶子节点的问题，所以要特判 
        cout << "Yes\n0\n";
        return 0;
    }
    //染色 
    er = &s;
    dfs0(1, 0);
    er = &t;
    dfs0(1, 0);
    for(int i = 1; i <= n*2; i++) ano[i] = ((i-1)^1)+1;
    for(int i = 1; i <= n; i++) sors[i] = srot[i] = i;
    sort(sors+1, sors+n+1, cmp);
    if(!check()){
        for(int i = 1; i <= n; i++) t.col[i] = t.col[i]^1;//如果不匹配也可能是初始颜色染反了，要反过来一次 
        if(!check()){
            cout << "No";
            return 0;
        }
    }
    dfs2(sors[1], -1, srot[1], -1);//注意传的是-1，因为0会导致死循环 
    cout << "Yes\n" << k << '\n';
    for(int i = 1; i <= k; i++) cout << ans[i].x << ' ' << ans[i].y << '\n';
    for(int o = 1; o <= n; o++){//由于叶子的对应关系不一定是预设的对应关系，所以要重新做 
        if(s.deg[sors[o]] != 1){
            oth[sors[o]] = srot[o];
            int i = s.head[sors[o]], j = t.head[srot[o]];
            while(i && s.deg[s.to[i]] != 1) i = s.nxt[i];//从上面的代码微调而来 
            while(j && t.deg[t.to[j]] != 1) j = t.nxt[j];
            for(; i; ){
                oth[s.to[i]] = t.to[j];
                assert(j != 0);
                do{ i = s.nxt[i];
                }while(i && s.deg[s.to[i]] != 1);
                do{ j = t.nxt[j];
                }while(j && t.deg[t.to[j]] != 1);
            }
        }
    }
    for(int i = 1; i <= n; i++){
        cout << oth[i] << ' ';
    }
    return 0;
}