队列实现，思路简单，kahn算法
#include <cstdio> #include <cstring> #include <vector> #include <queue> #include <iostream> using namespace std; #define DEBUG const int maxn=100+5; int m,n,a,b; int indegree[maxn]; int G[maxn][maxn]; void solve(){ queue<int> q; for(int i=1;i<=n;i++) if(indegree[i]==0) q.push(i); int kase=1; while(!q.empty()){ int u=q.front();q.pop(); cout<<u; if(kase==n)cout<<"\n"; else cout<<" "; kase++; for(int i=1;i<=n;i++){ if(G[u][i]==1) { indegree[i]--; if(indegree[i]==0) q.push(i); } } } } int main(){ #ifdef DEBUG freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); #endif while(cin>>n>>m){ memset(G,0,sizeof(G)); memset(indegree,0,sizeof(indegree)); while(m--){ cin>>a>>b; indegree[b]++; G[a][b]=1; } solve(); } #ifdef DEBUG fclose(stdin); fclose(stdout); #endif return 0; }dfs实现，白书的代码
#include <cstdio> #include <cstring> #include <vector> #include <queue> #include <iostream> using namespace std; #define DEBUG const int maxn=100+5; int m,n,a,b,t; int ans[maxn]; int G[maxn][maxn]; int c[maxn]; bool dfs(int u){ c[u]=-1; for(int v=1;v<=n;v++){ if(G[u][v]==1){ if(c[v]==-1) return false; else if(c[v]==0){ if(!dfs(v)) return false; } } } c[u]=1; ans[t--]=u; return true; } bool solve(){ t=n; for(int i=1;i<=n;i++) if(c[i]==0){ if(!dfs(i)) return false; } return true; } int main(){ #ifdef DEBUG freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); #endif while(cin>>n>>m){ memset(G,0,sizeof(G)); memset(c,0,sizeof(c)); while(m--){ cin>>a>>b; G[a][b]=1; } if(solve()){ for(int i=1;i<=n;i++) { cout<<ans[i]; if(i==n)cout<<"\n";else cout<<" "; } } } #ifdef DEBUG fclose(stdin); fclose(stdout); #endif return 0; }