样例过了,但是全TLE
查看原帖
样例过了,但是全TLE
633466
LiaoYF1楼主2023/5/13 09:51
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
struct edge{
    int to,id;
};
int n,m,cnt,vis[200005],ans[200005],flag,d[100005];
vector<edge> a[100005];
bool cmp(edge x,edge y){
    return x.to<y.to;
}
void dfs(int x,int k){
    if(k==m+1||flag==1){
        flag=1;
        return;
    }
    for(int i=0;i<a[x].size();i++){
        if(flag==1)return;
        int v=a[x][i].to;
        if(!vis[a[x][i].id]){
            vis[a[x][i].id]=1;
            ans[k+1]=v;
            dfs(v,k+1);
            vis[a[x][i].id]=0;
        }
    }
}
int main(){
    //freopen("test.in","r",stdin);
    //freopen("test.out","w",stdout);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        a[u].push_back((edge){v,++cnt});
        d[v]++;d[u]++;
    }
    for(int i=1;i<=n;i++){
        sort(a[i].begin(),a[i].end(),cmp);
    }
    int start=0;
    for(int i=1;i<=n;i++){
        if(d[i]%2==1){
            start=i;
            break;
        }
    }
    if(start==0){
        for(int i=1;i<=n;i++){
            if(d[i]!=0){
                start=i;
                break;
            }
        }
    }
    ans[1]=start;
    dfs(start,1);
    if(flag==0){
        cout<<"No";
        return 0;
    }
    for(int i=1;i<=m+1;i++){
        cout<<ans[i]<<" ";
    }
    return 0;
}
2023/5/13 09:51
加载中...