题目连接 ： http://acm.hdu.edu.cn/showproblem.php?pid=1285
拓扑排序，很明显的一道拓扑排序的问题，用一个二维数组存储两个数字之间的关系，如果某个数大于另一个数，那么它们之间的关系为1，否则为0.
如果存在关系为1的两个数据，那么行表示比列大。列的下标入度自增1.然后使用拓扑排序思想依次取出每个节点。
此题可参考类似题目 http://www.cnblogs.com/newpanderking/archive/2012/10/16/2726757.html 这也是一道经典的拓扑排序
#include <cstdio> #include <cstring> #include <algorithm> #define maxn 510 using namespace std; /* 拓扑排序解法 */ int rela[maxn][maxn]; int in_degree[maxn],ans[maxn]; int n,m,x,y; void top_order() { //预处理 for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(rela[i][j])in_degree[j]++; for(int i=1;i<=n;i++) { int k=1; while(in_degree[k]!=0)k++; ans[i]=k; in_degree[k]--;//更新为-1，后边检测时不受影响 for(int j=1;j<=n;j++) if(rela[k][j]) in_degree[j]--;//相关联的入度减1 } } int main() { while(scanf("%d%d",&n,&m)!=EOF) { memset(in_degree,0,sizeof(in_degree)); memset(ans,0,sizeof(ans)); memset(rela,0,sizeof(rela)); for(int i=0;i<m;i++) { scanf("%d%d",&x,&y); rela[x][y]=1; } top_order(); for(int i=1;i<n;i++) printf("%d ",ans[i]); printf("%d\n",ans[n]); } return 0; }
