注释版（邻接表_版本）：
1.#include<bits/stdc++.h> #define mem(a,b) memset(a,b,sizeof a); using namespace std; typedef long long ll; const int MAXV=1000; // 边结点 struct ENode { int adjvex; // 邻接点：弧头顶点(下标) int weight; // 权值 ENode *next; // 链域，下一个邻接点 }; // 顶点结点 typedef struct VNode { int in; // 入度 int data; // 顶点信息 ENode *firstE; // 边表头指针 }AdjList[MAXV]; // 邻接表 typedef struct gAList { AdjList adjList; int numV,numE; // 顶点数 边数 }*GAList; int TopoSort(GAList GAL) // 拓扑排序 { ENode *e; int top=0; // 用于sk栈指针下标 int cnt=0; // 统计输出顶点的个数 int *sk; // 建栈，存储入度为0的顶点 sk=(int *)malloc(GAL->numV*sizeof(int)); for(int i=0;i<GAL->numV;i++) if(GAL->adjList[i].in==0) sk[++top]=i; // 将入度为0的顶点入栈；++top 从1开始，为下文 while(top!=0) 做准备 while(top!=0) { int gettop=sk[top--]; // 出栈 printf("%d -> ",GAL->adjList[gettop].data); cnt++; // 统计输出顶点数 for(e=GAL->adjList[gettop].firstE; e; e=e->next) // 对此顶点弧表遍历 { int k=e->adjvex; if(!(--GAL->adjList[k].in)) // 将k号顶点邻接点的入度-1 sk[++top]=k; // 若为0则入栈，方便下次循环输出 } } if(cnt<GAL->numV) // 若 cnt 小于顶点数，则存在环 return 0; else return 1; }
简化版（邻接表_版本）：
#include<bits/stdc++.h> #define mem(a,b) memset(a,b,sizeof a); using namespace std; typedef long long ll; const int MAXV=1000; struct ENode { int adjvex; int weight; ENode *next; }; typedef struct VNode { int in; int data; ENode *firstE; }AdjList[MAXV]; typedef struct gAList { AdjList adjList; int numV,numE; }*GAList; int TopoSort(GAList GAL) { ENode *e; int top=0; int cnt=0; int *sk; sk=(int *)malloc(GAL->numV*sizeof(int)); for(int i=0;i<GAL->numV;i++) if(GAL->adjList[i].in==0) sk[++top]=i; while(top!=0) { int gettop=sk[top--]; printf("%d -> ",GAL->adjList[gettop].data); cnt++; for(e=GAL->adjList[gettop].firstE; e; e=e->next) { int k=e->adjvex; if(!(--GAL->adjList[k].in)) sk[++top]=k; } } if(cnt<GAL->numV) return 0; else return 1; }
释版（邻接矩阵_版本）：
#include<bits/stdc++.h> #include<cmath> #define mem(a,b) memset(a,b,sizeof a) using namespace std; typedef long long ll; const int MAXV=1010; // 邻接矩阵 int mp[MAXV][MAXV]; // 边结点 int in[MAXV]; // 入度 int n,m; void TopoSort() { int top=-1; // 回路标记 for(int i=0;i<n;i++) { if(in[i]==0) { in[i]=top; // 类似next[]存储 top=i; // FILO思想 } } for(int i=0;i<n;i++) { if(top==-1) // 存在回路 { return ; } else { int j=top; top=in[top]; // 每次都是 -1，做标记，看接下来for_k是否有符合的新零度点。若没有，存在回路 printf("%d ",j); // 输出结果 for(int k=0;k<n;k++) { if(mp[j][k] && --in[k]==0) // 将j号顶点邻接点k的入度-1 { in[k]=top; // 同上 top=k; // 同上 } } } } }
简化版（邻接矩阵_版本）：
#include<bits/stdc++.h> #include<cmath> #define mem(a,b) memset(a,b,sizeof a) using namespace std; typedef long long ll; const int MAXV=1010; int mp[MAXV][MAXV]; int in[MAXV]; int n,m; void TopoSort() { int top=-1; for(int i=0;i<n;i++) { if(in[i]==0) { in[i]=top; top=i; } } for(int i=0;i<n;i++) { if(top==-1) { return ; } else { int j=top; top=in[top]; printf("%d ",j); for(int k=0;k<n;k++) { if(mp[j][k] && --in[k]==0) { in[k]=top; top=k; } } } } }
简化版（邻接矩阵_优先队列_版本）：
#include<bits/stdc++.h> #include<cmath> #define mem(a,b) memset(a,b,sizeof a) #define ssclr(ss) ss.clear(), ss.str("") #define INF 0x3f3f3f3f #define MOD 1000000007 using namespace std; typedef long long ll; const int maxn=520; int n; int g[maxn][maxn], in[maxn]; priority_queue<int,vector<int>,greater<int>> pq; vector<int> vec; void init() { mem(g,0), mem(in,0); while(!pq.empty()) pq.pop(); vec.clear(); } void topo() { for(int i=1;i<=n;i++) if(in[i]==0) pq.push(i); int tp; while(!pq.empty()) { tp=pq.top(); pq.pop(); vec.push_back(tp); for(int i=1;i<=n;i++) if(g[tp][i] && --in[i]==0) pq.push(i); } } int main() { int m,u,v; while(~scanf("%d%d",&n,&m)) { init(); for(int i=0;i<m;i++) { scanf("%d%d",&u,&v); if(g[u][v]==0 && u!=v) { g[u][v]=1; in[v]++; } } topo(); if(vec.size()!=n) puts("-1"); else { for(int i=0;i<vec.size();i++) printf("%d%c",vec[i],i==vec.size()-1?'\n':' '); } } return 0; }
Ps：注意去重！
