大致题意：每个样例包含两行，第一行输入n个字符，可能是无序的。第二行输入成对的a b,代表a要在b前面。输出所有的符合这样的序列。
思路：很明显的拓扑排序。要输出所有的序列，那么就从入度为0的点进行dfs，每次选择一个入度为0的点，加入输出序列并把与它相邻的点的入度减一。dfs结束后要把状态再改回来。
#include #include #include #include #include #include #include #include #include #define LL long long #define _LL __int64 using namespace std; const int maxn = 110; char contents[30]; bool mapp[60][60]; int n = 0; char t,t1,t2; int flag; int in[30]; int vis[30]; int ans[30]; void dfs(int num) { if(num == n) { for(int i = 0; i < n; i++) printf("%c",ans[i]); printf("\n"); return; } for(int i = 0; i < n; i++) { if(!vis[i] && !in[ contents[i]-'a' ]) { for(int j = 0; j < n; j++) { if(mapp[contents[i]-'a'][contents[j]-'a']) { in[ contents[j]-'a']--; } } ans[num] = contents[i]; vis[i] = 1; dfs(num+1); //注意将状态更改回来 for(int j = 0; j < n; j++) { if(mapp[contents[i]-'a'][contents[j]-'a']) { in[ contents[j]-'a']++; } } vis[i] = 0; } } } int main() { flag = 0; while(~scanf("%c",&t)) { if(t >= 'a' && t <= 'z') { contents[n++] = t; continue; } else if(t == ' ') continue; else { if(flag) printf("\n"); flag = 1; sort(contents,contents+n); //因为输入可能是无序的，先排序 memset(in,0,sizeof(in)); memset(mapp,false,sizeof(mapp)); memset(vis,0,sizeof(vis)); while(~scanf("%c %c",&t1,&t2)) { mapp[t1-'a'][t2-'a'] = 1; in[t2-'a']++; if(getchar() == '\n') break; } dfs(0); n = 0; } } return 0; }