|算法讨论|拓扑排序学习笔记

2019-11-14 10:06:36

字体：大中小

来源：转载

供稿：网友

hdu1285

#include<cstdio> #include<algorithm> #include<cstring> #include<vector> #define ms(i,j) memset(i,j, sizeof i); using namespace std; const int MAXN = 500 + 5;int map[MAXN][MAXN], ino[MAXN]; int n,m; int k = 0;int PR[MAXN];int topsort(){ for (int i=1;i<=n;i++) { for (int j=1;j<=n;j++) { if (ino[j]==0) { ino[j]--; pr[++k] = j; for (int u=1;u<=n;u++) if (map[j][u]) ino[u]--; break; } } } if (k<n) return -1;//有环 return 0;}int main() { while (scanf("%d%d", &n, &m)==2) { ms(ino,0); ms(map,0); ms(pr,0); k = 0; for (int i=1;i<=m;i++) { int x,y; scanf("%d%d", &x,&y); if (!map[x][y])//小心重边！ { map[x][y] = 1; ino[y]++; } } topsort(); for(int i=1;i<=n;i++) { printf("%d", pr[i]); if (i!=n) putchar(' '); } printf("/n"); } return 0; }

上一篇：P1586 魔法照片

下一篇：java中的常量