题目链接；
POJ 1270 Following Orders
题意：
给出 n 个不同的小写字母和若干约数关系，表示某些字母不能排在某些字母前面。按字典序输出所有可能的排列。
数据范围:
分析：
有两种思路。
用 link[i][j] 表示编号为 i 的字母不能排在编号为
也可以利用 next_permutation() 函数生成所有的排列，然后判断是否合法即可。因为 next_permutation() 函数是生成到字典序最大时结束，所以也需要从最小的字典序开始生成。不过这样的效率好像不如 dfs ，但是对于本题的数据足够了。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <climits>
#include <cmath>
#include <ctime>
#include <cassert>
#include <map>
#include <sstream>
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
typedef long long ll;
const int MAX_N = 30;
const int MAX_M = 350;int total, len;
string ans;
int link[MAX_N][MAX_N], vis[MAX_N];void dfs(int cur)
{if(cur == total) {for(int i = 0; i < total; ++i) {cout << ans[i];}cout << endl;return;}for(int i = 0; i < 26; ++i) {if(vis[i] == 0) continue;int flag = 0;for(int j = 0; j < cur; ++j) {int t = ans[j] - 'a';if(link[t][i]) {flag = 1;break;} }if(flag) continue;else {ans[cur] = i + 'a';dfs(cur + 1);}}return;
}int main()
{string s;int begin = 1;while(getline(cin, s)) {memset(vis, 0, sizeof(vis));memset(link, 0, sizeof(link));len = s.size(), total = 0;for(int i = 0; i < len; ++i) {if(s[i] == ' ') continue;vis[s[i] - 'a'] = 1;total++;}getline(cin, s);len = s.size();int flag = 0, id1, id2;for(int i = 0; i < len; ++i) {if(s[i] == ' ') continue;id1 = s[i] - 'a';i++;while(s[i] == ' ') i++;id2 = s[i] - 'a';link[id2][id1] = 1; //不能让id2排在id1之前}for(int i = 0; i < 26; ++i) { link[i][i] = 1; }if(begin) begin = 0;else cout << endl;dfs(0); //当前已经有0个排好了}return 0;
}
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <climits>
#include <cmath>
#include <ctime>
#include <cassert>
#include <sstream>
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
typedef long long ll;
const int MAX_N = 30;int vis[MAX_N], data[MAX_N], total, link[MAX_N][MAX_N];
string s;bool check()
{for(int i = 0; i < total; ++i){for(int j = i + 1; j < total; ++j) {if(link[data[i]][data[j]]) return false;}}return true;
}int main()
{int first = 1;while(getline(cin, s)) {memset(vis, 0, sizeof(vis));total = 0;int len = s.size();for(int i = 0; i < len; ++i) {if(s[i] == ' ') continue;vis[s[i] - 'a'] = 1;}for(int i = 0; i < 26; ++i) {if(vis[i]) {data[total++] = i;}}memset(link, 0, sizeof(link));getline(cin, s);len = s.size();for(int i = 0; i < len; ++i) {if(s[i] == ' ') continue;int id1 = s[i] - 'a';i++;while(s[i] == ' ') i++;int id2 = s[i] - 'a';link[id2][id1] = 1; //id2不允许出现在id1之前}if(first) first = 0;else cout << endl;do {if(check()) {for(int i = 0; i < total; ++i) {char c = data[i] + 'a';cout << c;}cout << endl;}}while(next_permutation(data, data + total));}return 0;
}