嗯…nice~ 对于临接链表在这里存图非常不爽 由于你需要使用sort对当前节点进行处理,使用贪心(走最小字典序) 所以你需要再开一个数组进行存入以便于排序,那么这个数组就显得至关重要,数组开大了就TLE,而且也不能太小,所以我们就尝试去开成50左右,至少不会超时间 (但别人想卡死你那就没招了)由于不太会用vector之类的矩阵存图我还是用邻接链表; 同时给大家安利一波register int; 这个手动优化可以加快for循环的速度; 对于测试数据最后一个点大概快了100ms左右; 下面进入正题… 操作前看一波数据范围n==m; 基环树!!! 对于这种数据结构第一件事就是找环; 之后就是依次断开所有的链去暴搜; 代码如下
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #define rei register int using namespace std; int n,m;int stack[50001];int dfn[50001]; int ans[50001],top;int times,cnt,stop,flag; int tot,head[50001];int dad[50001]; struct node { int ver; int next; }edge[50001]; bool cmp(int x,int y) { return x<y; } inline void add(int x,int y) { edge[++tot].next=head[x]; edge[tot].ver=y; head[x]=tot; } inline void dfs1(int x,int fa) { ans[++top]=x; int vis[55];memset(vis,0,sizeof(vis)); int num=0; for(rei i=head[x];i;i=edge[i].next) { int y=edge[i].ver; if(fa==y) continue; vis[++num]=y; } sort(vis+1,vis+num+1,cmp); for(rei i=1;i<=num;++i) dfs1(vis[i],x); } inline void find_loop(int x) { dfn[x]=++times; for(rei i=head[x];i;i=edge[i].next) { int y=edge[i].ver; if(y==dad[x]) continue; if(dfn[y]) { if(dfn[y]<dfn[x]) continue; stack[++cnt]=y; for(;y!=x;y=dad[y]) stack[++cnt]=dad[y]; } else dad[y]=x,find_loop(y); } } inline void dfs2(int x,int fa,int ban1,int ban2) { if(stop) return; top++; if(x<ans[top]) flag=1; if(x>ans[top]&&!flag) { stop=1;return ;}//剪枝如果本次dfs所确定的顺序大于之前的直接return if(flag) ans[top]=x; int vis[55],num=0,ban=0; memset(vis,0,sizeof(vis)); //下面是枚举断链的精髓 if(x==ban1) ban=ban2; else if(x==ban2) ban=ban1; for(rei i=head[x];i;i=edge[i].next) { int y=edge[i].ver; if(y==fa) continue; if(y!=ban) vis[++num]=y; } sort(vis+1,vis+num+1,cmp); for(rei i=1;i<=num;++i) dfs2(vis[i],x,ban1,ban2); } int main() { cin>>n>>m; int u,v; for(int i=1;i<=m;++i) { scanf("%d%d",&u,&v); add(u,v); add(v,u); } if(m==n-1) { dfs1(1,0); for(int i=1;i<=n;++i) cout<<ans[i]<<" "; } if(n==m) { int vis[5001];memset(vis,0,sizeof(vis)); memset(ans,0x3f,sizeof(ans));//初始化 find_loop(1); for(rei i=1;i<cnt;++i) { flag=top=stop=0; dfs2(1,1,stack[i],stack[i+1]); } for(rei i=1;i<=n;++i) cout<<ans[i]<<" "; } return 0; }PS:第一次写题解and本题代码思路有对别人的借鉴; 我希望在细节上对大家有帮助