UVA124 Following Orders 题解
题意：
顺序是数学和计算机科学中的一个重要概念。例如，佐恩引理（Zorn’s Lemma）指出：“一个偏序集合中，每个链都有一个上界，那么该集合中必存在一个极大元素”。顺序在推理程序的不动点语义中也很重要。
这个问题既不涉及佐恩引理，也不涉及不动点语义，但涉及到顺序。给定一组形式为 $x<y$ 的变量约束，你需要编写一个程序，打印出与这些约束一致的变量排序。
例如，给定约束 $x<y$ 和 $x<z$，存在两种与这些约束一致的变量 $x$、$y$ 和 $z$ 的排序：$x \ y \ z$ 和 $x \ z \ y$。
输入格式：
输入由一系列约束规范组成。每个规范由两行组成：第一行是变量列表，第二行是约束列表。约束由一对变量组成，其中 “$x y$” 表示 $x<y$。
所有的变量都是小写字母，并且只包含一个字符。每个规范中至少会有两个变量，且不超过 20 个变量。每个规范中至少会有一个约束，且不超过 50 个约束。每个规范中与约束一致的排序至少有一个，且不超过 300 种。
输入以文件结束符（end-of-file）终止。
输出格式：
对于每个约束规范，应打印与约束一致的所有排序。排序按字典顺序（按字母顺序）逐行打印。
不同约束规范的输出之间用空行分隔。
我一开始想的是建一个图，然后自由跑。后来我发现，这个东西还不如直接暴力枚举呢。。
时间复杂度 $\mathcal{O}(26^n)$ ，$n$ 为变量数
代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(35))
char avi[N],vis[N],g[N][N]; int num,ans[N];
bool check(int a,int b)
{
for(int i = 0; i < a; i++)
if(g[b][ans[i]]) return false;
return true;
}
void clear()
{
num = 0;
memset(avi, 0, sizeof(avi)); memset(g, 0, sizeof(g));
memset(vis, 0, sizeof(vis)); memset(ans, 0, sizeof(ans));
}
void dfs(int now)
{
if(now == num)
{
for(int i = 0; i < now; i++) cout << char(ans[i] + 'a');
return cout << '\n', void(0);
}
for(int i = 0; i < 26; i++)
if(avi[i] && !vis[i] && check(now, i))
{
vis[i] = true; ans[now] = i;
dfs(now + 1); vis[i] = false;
}
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
string str; bool cxy = false;
while(getline(cin, str))
{
if(cxy) { cout << '\n'; } clear();
int len = str.size();
for(int i = 0; i < len; i++)
if(str[i] != ' ') { ++num; avi[str[i] - 'a'] = true; }
getline(cin, str); len = str.size();
for(int i = 0; i < len; i += 4) g[str[i] - 'a'][str[i + 2] - 'a'] = true;
dfs(0); cxy = true;
}
return 0;
}参考文献：
