問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1270思路:
拓撲排序適合于描述事件發生的先后次序
這題，對于a>b這樣的題目要求，就非常適合用拓撲排序來進行
一次AC，寫的過程還接了個女朋友的電話，跟同學聊了會天，o(∩_∩)o...哈哈
代碼:
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<string.h>
4 #define STR_LEN 207
5 #define MAX_N 26
6 int adj[MAX_N][MAX_N], in_dgr[MAX_N];
7 int visited[MAX_N];
8 int total, ch[MAX_N];
9 char ans[MAX_N];
10
11 int
12 init()
13 {
14 int i, f, t, len;
15 char str[STR_LEN];
16 total = 0;
17 memset(ch, 0, sizeof(ch));
18 memset(in_dgr, 0, sizeof(in_dgr));
19 memset(adj, 0, sizeof(adj));
20 memset(visited, 0, sizeof(visited));
21 memset(ans, 0, sizeof(ans));
22 if(fgets(str, STR_LEN, stdin) == NULL)
23 return 0;
24 len = strlen(str);
25 for(i=0; i<len; i+=2) {
26 if(str[i]>='a' && str[i]<='z') {
27 ++total;
28 ++ch[str[i]-'a'];
29 }
30 }
31 fgets(str, STR_LEN, stdin);
32 len = strlen(str);
33 for(i=0; i<len; i+=2) {
34 if((i>>1)%2 == 0)
35 f = str[i]-'a';
36 else {
37 t = str[i]-'a';
38 adj[f][t] = 1;
39 ++in_dgr[t];
40 }
41 }
42 return 1;
43 }
44
45 void
46 topo_sort(int depth)
47 {
48 int i, j;
49 if(depth == total) {
50 printf("%s\n", ans);
51 return;
52 }
53 for(i=0; i<MAX_N; i++) {
54 if(ch[i] && !visited[i] && !in_dgr[i]) {
55 visited[i] = 1;
56 ans[depth] = 'a'+i;
57 for(j=0; j<MAX_N; j++)
58 if(adj[i][j])
59 --in_dgr[j];
60 topo_sort(depth+1);
61 visited[i] = 0;
62 for(j=0; j<MAX_N; j++)
63 if(adj[i][j])
64 ++in_dgr[j];
65 }
66 }
67 }
68
69 int
70 main(int argc, char **argv)
71 {
72 while(init()) {
73 topo_sort(0);
74 printf("\n");
75 }
76 }