这个和题解top1有啥区别┭┮﹏┭┮60
查看原帖
这个和题解top1有啥区别┭┮﹏┭┮60
844814
threading楼主2023/9/5 21:48
#include <bits/stdc++.h>
using namespace std;
const int N=2e5+10;
vector<int> g[N];
int din[N],dout[N];
int pos[N];
int n,m;
stack<int> ans;
void dfs(int u){
    for(int i=pos[u];i<g[u].size();i=pos[u]){
        pos[u]=i+1;
        dfs(g[u][i]);
    }
    ans.push(u);
}
int main()
{
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        g[a].push_back(b);
        din[b]++,dout[a]++;
    }
    for(int i=1;i<=n;i++) sort(g[i].begin(),g[i].end());
    int s=1;
    int cnt[]={0,0};
    bool ok=false;
    for(int i=1;i<=n;i++){
        if(din[i]!=dout[i]){
            ok=false;
            if(dout[i]-din[i]==1) cnt[1]++,s=i;
            else if(din[i]-dout[i]==1) cnt[0]++;
            else{
                cout<<"No"<<endl;
                return 0;
            }
        }
    }
    if(!ok&&!(cnt[0]==cnt[1]&&cnt[0]==1)){
        cout<<"No"<<endl;
        return 0;
    }
    dfs(s);
    while(!ans.empty()) cout<<ans.top()<<' ',ans.pop();
    cout<<endl;
    return 0;
}
2023/9/5 21:48
加载中...