hdu1285拓扑排序
1 #include "iostream" 2 #include "vector" 3 #include "memory.h" 4 #include "cstdio" 5 using namespace std; 6 #define swap(a,b,t) ( (t) = (x),(x) = (y),(y) = (t) ) 7 #define MAXN 510 8 int G[MAXN][MAXN]; 9 int indegree[MAXN]; 10 int ans[MAXN],t; 11 int n,m; 12 13 bool toposort() 14 { 15 for (int i = 0;i <= n; ++ i) 16 for (int j = 0;j <= n; ++ j) { 17 if(G[i][j]) indegree[j]++; 18 } 19 for (int i = 0;i < n; ++ i) { 20 int num = 1; 21 while (indegree[num] != 0) 22 num ++; 23 ans[i] = num; 24 indegree[num] = -1; 25 for (int j = 0;j <= n; ++ j) { 26 if (G[num][j] == 1) indegree[j]--; 27 } 28 } 29 return true; 30 } 31 32 33 int main() 34 { 35 while (cin >> n >> m) { 36 memset(indegree,0,sizeof(indegree)); 37 memset(G,0,sizeof(G)); 38 memset(ans,0,sizeof(ans)); 39 for (int i = 0;i < m; ++ i) { 40 int a,b; 41 cin >> a >> b; 42 G[a][b] = 1; 43 } 44 if (toposort()) { 45 for (int i = 0;i < n; ++ i) { 46 cout << ans[i]; 47 if (i != n-1) cout << " "; 48 else cout << endl; 49 } 50 } 51 } 52 return 0; 53 }
1 #include "iostream" 2 #include "vector" 3 #include "memory.h" 4 #include "cstdio" 5 using namespace std; 6 #define swap(a,b,t) ( (t) = (x),(x) = (y),(y) = (t) ) 7 #define MAXN 510 8 int G[MAXN][MAXN]; 9 int indegree[MAXN]; 10 int ans[MAXN],t; 11 int n,m; 12 13 bool toposort() 14 { 15 for (int i = 0;i <= n; ++ i) 16 for (int j = 0;j <= n; ++ j) { 17 if(G[i][j]) indegree[j]++; 18 } 19 for (int i = 0;i < n; ++ i) { 20 int num = 1; 21 while (indegree[num] != 0) 22 num ++; 23 ans[i] = num; 24 indegree[num] = -1; 25 for (int j = 0;j <= n; ++ j) { 26 if (G[num][j] == 1) indegree[j]--; 27 } 28 } 29 return true; 30 } 31 32 33 int main() 34 { 35 while (cin >> n >> m) { 36 memset(indegree,0,sizeof(indegree)); 37 memset(G,0,sizeof(G)); 38 memset(ans,0,sizeof(ans)); 39 for (int i = 0;i < m; ++ i) { 40 int a,b; 41 cin >> a >> b; 42 G[a][b] = 1; 43 } 44 if (toposort()) { 45 for (int i = 0;i < n; ++ i) { 46 cout << ans[i]; 47 if (i != n-1) cout << " "; 48 else cout << endl; 49 } 50 } 51 } 52 return 0; 53 }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。