提交记录

不知道为什么普通版一开始也是WA18,19,23

普通版可过，加强版基环树情况WA 3点

思路

先求出环上点，深搜同时记录下最近未走过的最小点 $t$ ,如果下一个点 $u$ 比 $t$ 大就回溯一次。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll m,n,fl;
bool vis[500005],p[500005];
vector<ll> f[500005];
stack <ll> q;
void fc1(ll x){//树情况
    vis[x]=1;
    cout<<x<<" ";
    for(int i=0;i<f[x].size();i++){
        if(!vis[f[x][i]])fc1(f[x][i]);
    }
}
void fc2(ll x,ll fr){//求环上点
    for(int i=0;i<f[x].size();i++){
        if(f[x][i]!=fr){
            q.push(f[x][i]);
            if(vis[q.top()]){
                fl=1;
                return ;
            }
            vis[f[x][i]]=1;
            fc2(f[x][i],x);
            if(fl)return ;
            q.pop();
            vis[f[x][i]]=0;
        }
    }
}
void fc3(ll x,ll t,ll fr){//基环树情况dfs
    cout<<x<<" ";
    //cout<<t<<endl;
    p[x]=1;
    for(int i=0;i<f[x].size();i++){
       if(p[f[x][i]])continue;
       if(fl||!vis[f[x][i]]){
            fc3(f[x][i],INT_MAX,x);
       }else{
            if(f[x][i]>t){
                //cout<<f[x].size()<<" "<<i<<"#\n";
                if(f[x].size()-i>=2&&fr<f[x][i])fr=fr;
                else{
                    fl=1;
                    return;
                }
                
            }
            if(f[x].size()-i>=2&&!p[f[x][i+1]])t=f[x][i+1];
            if(f[x].size()-i>=3&&p[f[x][i+1]])t=f[x][i+2];
            fc3(f[x][i],t,x);
       }
    }
}
void fc4(){//基环树情况深搜前置操作
    q.push(1);
    vis[1]=1;
    fc2(1,0);
    memset(vis,0,sizeof(vis));
    ll x=q.top();
    vis[q.top()]=1;
    while(!q.empty()){
        q.pop();
        vis[q.top()]=1;
        if(x==q.top())break;
    }
    fl=0;
    fc3(1,INT_MAX,0);
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        ll x,y;
        cin>>x>>y;
        f[x].push_back(y);
        f[y].push_back(x);
    }
    for(int i=1;i<=n;i++)sort(f[i].begin(),f[i].end());
    if(n-1==m){
        fc1(1);
    }else{
        fc4();
    }
    return 0;
}