解题报告

树的情况直接贪心做，基环树枚举环上的边断开然后贪心做。

乱优化代码害人不浅，少 $20$ 分送我爆炸。

测评鸭上面有 $O(n)$ 加强版，大佬们可以去切啊QAQ。

示例程序

#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=5000;

int n,m,fa[maxn+5],ti,vis[maxn+5],ans[maxn+5],top,stk[maxn+5];bool BCC[maxn+5],fl;
int E,lnk[maxn+5],son[(maxn<<1)+5],nxt[(maxn<<1)+5],now,p[maxn+5],pos;

#define Eoln(x) ((x)==10||(x)==13||(x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    return (l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r))?EOF:*l++;
}
template<typename T> inline int readi(T &x){
    T tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    return (lst=='-'?x=-tot:x=tot),Eoln(ch);
}
#define Add(x,y) (son[E]=(y),nxt[E]=lnk[x],lnk[x]=E++)
void getBCC(int x,int pre=0){
    for (int j=(vis[x]=ti,fa[x]=pre,lnk[x]);~j;j=nxt[j])
        if (son[j]!=pre) if (vis[son[j]]<ti) getBCC(son[j],x);
            else if (!BCC[x]) {for (int i=x;i!=son[j];i=fa[i]) BCC[i]=true;BCC[son[j]]=true;}
}
//原来在DFS里加了点没什么用的剪枝，直接爆炸
void Dfs(int x){
    p[pos++]=x;vis[x]=ti;int L=top+1,R=L;
    for (int j=lnk[x];~j;j=nxt[j]) if ((j>>1)!=now&&vis[son[j]]<ti) stk[R++]=son[j];
    sort(stk+L,stk+R);top=R-1;for (int i=L;i<R;i++) Dfs(stk[i]);top=L-1;
}
//新加check，DFS里不剪枝就tm的过了，仰天长叹
inline bool check(){
    for (int i=1;i<=n;i++)
        if (p[i]<ans[i]) return true; else if (p[i]>ans[i]) return false;return false;
}
int main(){
    freopen("travel.in","r",stdin);freopen("travel.out","w",stdout);
    readi(n);readi(m);E=0;memset(lnk,255,sizeof(lnk));ans[1]=2e9;
    for (int i=1,x,y;i<=m;i++) readi(x),readi(y),Add(x,y),Add(y,x);ti++;getBCC(1);
    for (int i=1;i<=n;i++)
        for (int j=lnk[i];~j;j=nxt[j])
            if (i<son[j]&&BCC[i]&&BCC[son[j]]){
                ti++;now=j>>1;pos=1;fl=true;
                if (Dfs(1),check()) for (int i=1;i<=n;i++) ans[i]=p[i];
            }
    ti++;now=-1;pos=1;fl=true;if (Dfs(1),check()) for (int i=1;i<=n;i++) ans[i]=p[i];
    for (int i=1,fst=true;i<=n;i++) fst?fst=false:putchar(' '),printf("%d",ans[i]);
    puts("");return 0;
}