rt

WA on #16#18，写的比较史

#include <algorithm>
#include <iostream>
#include <cstdio>
#include <vector>

#define N 500005

using namespace std;
int n,m,top,ans[N];

int vis[N]; bool Vis[N];
vector<int> e[N];

void dfs1(int u,int Fa) {
    ans[++top]=u,Vis[u]=1;
    for (int v:e[u]) {
        if (v==Fa or vis[v]==2 or Vis[v]) continue;
        dfs1(v,u);
    }
}

int fa[N];
int find(int x) { return fa[x]==x?x:fa[x]=find(fa[x]); }

void dfs2(int u,int Fa) {
    vis[u]=1;
    for (int v:e[u]) {
        if (v==Fa) continue;
        if (!vis[v]) dfs2(v,u);
        vis[u]=max(vis[v],vis[u]);
    }
}

void dfs3(int u,int Fa,int lim) {
    ans[++top]=u,Vis[u]=1; int tlim=lim;
    for (int v:e[u]) {
        if (v==Fa or Vis[v]) continue;
        lim=max(lim,v);
    }
    for (int v:e[u]) {
        if (v==Fa or Vis[v]) continue;
        if (vis[v]==2) {
            if (v>=lim) continue;
            dfs3(v,u,lim);
        } else dfs1(v,u);
    }
}

void dfs4(int u,int Fa) {
    ans[++top]=u,Vis[u]=1;
    if (vis[u]==2) {
        int mx=0,cmx=0;
        for (int v:e[u]) {
            if (v==Fa or Vis[v]) continue;
            if (vis[v]==2) {
                if (v>mx) cmx=mx,mx=v;
                else if (v>cmx) cmx=v;
            }
        }
        int mn=mx;
        for (int v:e[u]) {
            if (v==Fa or Vis[v]) continue;
            if (v>cmx) mn=min(mn,v);
        }
        for (int v:e[u]) {
            if (v==Fa or Vis[v]) continue;
            if (vis[v]==2)  {
                if (v==cmx) dfs3(v,u,mn);
                else dfs3(v,u,1e9);
            } else dfs4(v,u);
        }
    } else for (int v:e[u]) {
        if (v==Fa or Vis[v]) continue;
        dfs4(v,u);
    }
}

int main() {
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++) fa[i]=i;
    for (int i=1,u,v;i<=m;i++) {
        scanf("%d%d",&u,&v);
        e[u].push_back(v); e[v].push_back(u);
        int fu=find(u),fv=find(v);
        if (fu!=fv) fa[fu]=fv;
        else vis[u]=vis[v]=2;
    }
    for (int i=1;i<=n;i++) sort(e[i].begin(),e[i].end());
    for (int i=1;i<=n;i++)
        if (vis[i]==2) { dfs2(i,0); break; }
    for (int i=1;i<=n;i++) vis[i]=max(vis[i],1);
    dfs4(1,0);
    if (top<n) exit(-1);
    for (int i=1;i<=top;i++) printf("%d ",ans[i]);
    printf("\n");
    return 0;
}