TLE20分,请大佬指点
查看原帖
TLE20分,请大佬指点
487959
yyc_qwq楼主2022/12/29 21:57
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

vector<int> V[100005];
int a[100005],n,m,f[200005],vf[100005];

void dfs(int x,int sum){
    if(!(V[x].size()-vf[x])){
        if(sum>m){
            for(int i = 1;i <= m+1;i++){
                cout << f[i] << ' ';
            }
            cout << endl;
            exit(0);
        }
        return;
    }
    int tvf = vf[x];
    for(int i = vf[x];i < V[x].size();i++){
        int t = V[x][i];
        f[sum] = t;
        vf[x] = i+1;
        dfs(t,sum+1);
    }
    vf[x] = tvf;
}

int main() {
    int u,v,in = 0,out = 0,ini=-1,outi=-1;
    cin >> n >> m;
    for(int i = 1;i <= m;i++){
        cin >> u >> v;
        V[u].push_back(v);
        a[v]++;
    }
    for(int i = 1;i <= n;i++){
        sort(V[i].begin(),V[i].end());
        if(V[i].size()>a[i]) {
            if(V[i].size()-a[i]==1&&!in){
                if(ini==-1)ini=i;
                in++;
            }else{
                cout << "No" << endl;
                return 0;
            }
        }else if(V[i].size()<a[i]) {
            if(V[i].size()-a[i]==-1&&!out){
                if(outi==-1)outi=i;
                out++;
            }else{
                cout << "No" << endl;
                return 0;
            }
        }
    }
    if((ini==-1)+(outi==-1)==1){
        cout << "No" << endl;
        return 0;
    }
    if(ini==-1){
        f[1] = 1;
        dfs(1, 2);
    }else{
        f[1] = ini;
        dfs(ini, 2);
    }
    return 0;
}
2022/12/29 21:57
加载中...