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 }

DFS

 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 }

暴力