题意：
给出一些字母和这些字母之间的大小关系，要求输出所有满足大小的序列。
要点：
这题其实跟拓扑排序关系不是很大了，主要是输出所有序列比较麻烦，注意题目要求要输出所有的字母，也即是没有在大小关系中出现的字母可以插在任意位置上。我们可以这么想：所有当前入度为0的点可以作为起点，假设一个点的入度为3，说明它的前面起码有3个字母，每次dfs递归深度，寻找下一个入度为0的点，最后再回溯即可。
16128464Seasonal1270Accepted172K0MSC++1302B2016-09-27 19:52:09 #include<iostream> #include<cstring> #include<map> #include<algorithm> using namespace std; const int N = 25; bool graph[N][N]; char str[N], ans[N]; int indegree[N]; int res; map<char,int> num; void toposort(int depth) { if (depth == res)//题目中所有字母都会出现 { printf("%s\n", ans); return; } for (int u = 0; u < res; u++) { if (indegree[u] == 0)//入度为0说明可以以当前点为起点 { indegree[u]--; ans[depth] = str[u]; for(int v=0;v<res;v++) if (graph[u][v]) indegree[v]--; toposort(depth + 1); indegree[u]++; //回溯 for (int v = 0; v<res; v++) if (graph[u][v]) indegree[v]++; } } } int main() { char temp[55]; while(gets_s(temp)) { memset(graph, false, sizeof(graph)); memset(indegree, 0, sizeof(indegree)); int len = strlen(temp); res = 0; for (int i = 0; i < len; i++) if (isalpha(temp[i])) str[res++] = temp[i]; sort(str, str + res); //确保按照字典序输出 for (int i = 0; i < res; i++) num[str[i]] = i; gets_s(temp); len = strlen(temp); int flag = 0; int c1, c2; for (int i = 0; i < len; i++) { if (isalpha(temp[i])) { if (flag == 0) { c1 = num[temp[i]]; flag = 1; } else { c2 = num[temp[i]]; graph[c1][c2] = true; indegree[c2]++; flag = 0; } } } memset(ans, 0, sizeof(ans)); toposort(0); printf("\n"); } return 0; }
