——————————————————————————————————————————————————
给了最近怀疑码力的我一片希望,竟然一A了
(如果除去在loj上忘了加fre与在洛谷上忘了删fre)
暴力基环树,n^2logn
好吧当我没说,洛谷上MLE了
怎么这么毒瘤,空间这么小
————————————————————————————————————————————————
#include<bits/stdc++.h> using namespace std; int ne,a,b,n,m,head[15000],colar[15000],dd[15000][2],flg=0,tot=0,pos=1,tn=0; int ans[5001],last[5001]; int ma[5001][5001],bol[5001][5001]; struct node{int to,nxt;}eg[15000]; void adde(int u,int v){eg[++ne].to=v;eg[ne].nxt=head[u];head[u]=ne;} int cmp(int a,int b){return a<b;} stack<int>st; void dfs(int u,int fa) { cout<<u<<" "; int cnt=0; for(int i=head[u];i;i=eg[i].nxt)if(eg[i].to!=fa)ma[u][++cnt]=eg[i].to; sort(ma[u]+1,ma[u]+1+cnt,cmp); for(int i=1;i<=cnt;i++)dfs(ma[u][i],u); } void dfs2(int u,int fa){ if(flg)return; colar[u]=1; for(int i=head[u];i;i=eg[i].nxt) { int v=eg[i].to; if(v==fa)continue; if(!colar[v]){ st.push(v); dfs2(v,u); if(flg)return; st.pop(); } else{ dd[++tot][0]=u; dd[tot][1]=v; while(1) { int ta=st.top(); if(ta==v){flg=1;return;} st.pop(); dd[++tot][0]=ta; dd[tot][1]=st.top(); } } } } void dfs3(int u,int fa) { last[++tn]=u; int cnt=0; for(int i=head[u];i;i=eg[i].nxt)if(eg[i].to!=fa&&(!bol[u][eg[i].to]))ma[u][++cnt]=eg[i].to; sort(ma[u]+1,ma[u]+1+cnt,cmp); for(int i=1;i<=cnt;i++)dfs3(ma[u][i],u); } void dfs4(int u,int fa) { ans[++tn]=u; int cnt=0; for(int i=head[u];i;i=eg[i].nxt)if(eg[i].to!=fa&&(!bol[u][eg[i].to]))ma[u][++cnt]=eg[i].to; sort(ma[u]+1,ma[u]+1+cnt,cmp); for(int i=1;i<=cnt;i++)dfs4(ma[u][i],u); } int main() { //freopen("travel.in","r",stdin); //freopen("travel.out","w",stdout); cin>>n>>m;for(int i=1;i<=m;i++) {cin>>a>>b;adde(a,b);adde(b,a);} if(m==n-1)dfs(1,0); else{ st.push(1); dfs2(1,0); bol[dd[1][0]][dd[1][1]]=bol[dd[1][1]][dd[1][0]]=1; dfs3(1,0); bol[dd[1][0]][dd[1][1]]=bol[dd[1][1]][dd[1][0]]=0; for(pos=2;pos<=tot;pos++) { bol[dd[pos][0]][dd[pos][1]]=bol[dd[pos][1]][dd[pos][0]]=1; tn=0; dfs4(1,0); for(int i=1;i<=n;i++){ if(ans[i]>last[i])break; if(ans[i]<last[i]) {for(int j=1;j<=n;j++)last[j]=ans[j];break;} } bol[dd[pos][0]][dd[pos][1]]=bol[dd[pos][1]][dd[pos][0]]=0; } for(int i=1;i<=n;i++)cout<<last[i]<<" "; } }