P11425 题解

lmh_qwq · 2025-01-01 12:16:04 · 题解

参考了官方题解。

把拓扑序倒过来就是一个 dfs 序，容易发现这个 dfs 序上一个结点的父亲必须在它前面，没有其他限制。

拉出第一个 dfs 序来，设其为 {1,2,\cdots,n}。现在我们发现这里一个节点有多个可能的父亲，需要想办法把它们分开。

对于剩下的每条 dfs 序，考虑算出它的所有前缀最小值，发现这唯一确定了一条树上的链。所以可以对每个叶子做一次 dfs ，能得到大约 60 分。

实际上我们可以做得更好。考虑去掉叶子之后形成的树，对这棵树的每个叶子进行 dfs。考虑每个节点，在 dfs 到它的时候先搜原树上的叶子再搜其他邻居，这样就能算出每个叶子的父亲。

这样的话我们去掉所有叶子，剩下部分的叶子总数加上 1（最初的 dfs 序列）就是答案……吗？实际上对于非菊花图，剩余的叶子至少有两个，可以让一个作为第一个 dfs 序，这样可以再节省一个。

现在还有一个小问题，就是我们无法区分叶子节点的兄弟与父亲。这个是简单的，每次搜索完叶子之后打一个标记，让下一次以相反的顺序搜索即可。

然后就做完了。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=107;
ll T,n,m,timer,a[N],deg[N];
ll ans[N][N];
vector<ll> to[N],tmp;
void dfs(int u,int fa){
    tmp.clear();
    ans[m][timer--]=u;
    for (auto v:to[u]) if (v!=fa&&to[v].size()==1) tmp.emplace_back(v);
    if (a[u]&&tmp.size()) reverse(tmp.begin(),tmp.end());a[u]^=1;
    for (auto v:tmp) ans[m][timer--]=v;
    for (auto v:to[u]) if (v!=fa&&to[v].size()>1) dfs(v,u);
}
void solve(){
    m=0;
    memset(deg,0,sizeof(deg));
    for (int i=1;i<N;++i) to[i].clear();
    cin>>n;
    for (int u,v,i=1;i<n;++i){
        cin>>u>>v;++deg[u];++deg[v];
        to[u].emplace_back(v);to[v].emplace_back(u);
    }
    for (int i=1;i<=n;++i) if (deg[i]==n-1){
        cout<<"2\n";
        for (int j=1;j<=n;++j) if (i!=j) cout<<j<<" ";cout<<i<<'\n';
        for (int j=n;j;--j) if (i!=j) cout<<j<<" ";cout<<i<<'\n';
        return;
    }
    memset(deg,0,sizeof(deg));
    for (int i=1;i<=n;++i) if (to[i].size()!=1){
        for (auto j:to[i]) deg[i]+=(to[j].size()>=2);
        if (deg[i]==1){
            ++m;timer=n;
            dfs(i,0);
        }
    }
    cout<<m<<'\n';
    for (int i=1;i<=m;++i){
        for (int j=1;j<=n;++j) cout<<ans[i][j]<<' ';cout<<'\n';
    }
}
int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>T;
    while(T--) solve();
    return 0;
}