思路:
因为给定的是个有向图,所以一定有解,构造方案就是把这个u当前它欠钱的人先安排好,然后直接输出方案就是一组解了...其实就是按dfs序统计即可啦...
代码:
#include <bits/stdc++.h> using namespace std; const int N=1e5; vector<int>g[N]; int id,ans[N],use[N]; void dfs(int u) { if(use[u]) return; use[u]=true; for(int v:g[u]) if(!use[v]) dfs(v); ans[++id]=u; } int main() { int n,m; cin>>n>>m; for(int i=1;i<=m;i++) { int u,v; cin>>u>>v; g[u].push_back(v); } for(int i=1;i<=n;i++) if(!use[i]) dfs(i); for(int i=1;i<=n;i++) cout<<ans[i]<<' '; puts(""); return 0; }