拓扑排序

 1 #include <stdio.h>
 2 
 3 #define maxSize 105
 4 #define inf 0x7ffffff
 5 
 6 int v, e;
 7 
 8 int EDGE[maxSize][maxSize], inDegree[maxSize], visited[maxSize];
 9 
10 void topSort(void);
11 void initialize(void);
12 
13 int main() {
14     scanf("%d %d", &v, &e);
15 
16     initialize();
17 
18     int i;
19     for (i = 0; i < e; ++i) {
20         int from, to, weight;
21         scanf("%d %d %d", &from, &to, &weight);
22         EDGE[from][to] = weight;
23         ++inDegree[to];
24     }
25 
26     topSort();
27 
28     return 0;
29 }
30 
31 void topSort(void) {
32     int queue[maxSize] = {0}, head = -1, tail = 0;
33 
34     int i;
35     for (i = 0; i < v; ++i) {
36         if (!visited[i] && !inDegree[i]) {
37             head = 0;
38             queue[tail++] = i;
39             visited[i] = 1;
40         }
41     }
42     if (head < 0) {
43         printf("Impossible\n");
44         return ;
45     }
46 
47     while (head < tail) {
48         int t = queue[head++];
49         for (i = 0; i < v; ++i) {
50             if (!visited[i] && EDGE[t][i] < inf) {
51                 --inDegree[i];
52                 if (inDegree[i] == 0) {
53                     queue[tail++] = i;
54                     visited[i] = 1;
55                 }
56             }
57         }
58     }
59 
60     if (tail < v) {
61         printf("Impossible\n");
62     }
63     else {
64         for (i = 0; i < v; ++i) {
65             printf("%d ", queue[i]);
66         }
67         printf("\n");
68     }
69 }
70 
71 void initialize(void) {
72     int i, j;
73     for (i = 0; i < v; ++i) {
74         for (j = 0; j < v; ++j) {
75             if (i == j) {
76                 EDGE[i][j] = 0;
77             }
78             else {
79                 EDGE[i][j] = inf;
80             }
81         }
82     }
83 }