This problem involves neither Zorn's Lemma nor fix-point semantics, but does involve order.
Given a list of variable constraints of the form x < y, you are to write a program that prints all orderings of the variables that are consistent with the constraints.
For example, given the constraints x < y and x < z there are two orderings of the variables x, y, and z that are consistent with these constraints: x y z and x z y.
Input
All variables are single character, lower-case letters. There will be at least two variables, and no more than 20 variables in a specification. There will be at least one constraint, and no more than 50 constraints in a specification. There will be at least one, and no more than 300 orderings consistent with the contraints in a specification.
Input is terminated by end-of-file.
Output
Output for different constraint specifications is separated by a blank line.
Sample Input
a b f g
a b b f
v w x y z
v y x v z v w v
Sample Output
abfg
abgf
agbf
gabf wxzvy
wzxvy
xwzvy
xzwvy
zwxvy
zxwvy 思路：
简单的拓扑排序+dfs，通过入度判断，从1到26就有字典序，代码如下：
int in[], G[][], vis[], print[], num;
char ans[]; void init() {
num = ;
memset(in, , sizeof(in));
memset(G, , sizeof(G));
memset(vis, , sizeof(vis));
memset(print, , sizeof(print));
} void dfs(int u, int cnt) {
ans[cnt] = u - + 'a';
if(cnt == num) {
for(int i = ; i <= cnt; ++i)
cout << ans[i];
cout << "\n";
return;
}
// mark the point
print[u] = ;
for(int i = ; i <= ; ++i) {
if(vis[i] && G[u][i]) in[i]--;
}
for(int i = ; i <= ; ++i) {
if(vis[i] && !print[i] && !in[i]) {
dfs(i, cnt+);
}
// backtracing
}
for(int i = ; i <= ; ++i) {
if(vis[i] && G[u][i]) in[i]++;
}
print[u] = ;
} int main() {
ios::sync_with_stdio(false);
string t;
int t1, t2;
while(getline(cin, t)) {
init();
int siz = t.size();
for(int i = ; i < siz; i += ) {
vis[t[i] - 'a' + ] = ;
num++;
}
getline(cin, t);
siz = t.size();
for(int i = ; i + < siz; i += ) {
t1 = t[i] - 'a' + , t2 = t[i+] - 'a' + ;
G[t1][t2] = , in[t2]++;
}
for(int i = ; i <= ; ++i) {
if(vis[i] && !in[i]) {
dfs(i, );
}
}
cout << "\n";
} return ;
}