# 題目: UVa 872 - Ordering

# 題目說明

題目給數個字母及排列順序
求所有的可能排序

---

INPUT:
第一行有一個整數T，代表有T筆測資
接著有兩行字串，第一行為所有的字母，第二行為這些字母的排列順序
每個字母間以空格隔開

---

OUTPUT:
輸出所有可能的字母排序

# 解題方法

以字串儲存字母並排序
接著跑dfs，判斷字母是否有跑過、是否符合規則，都是則繼續跑下一層dfs

# 參考程式碼

#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <memory.h>

using namespace std;

bool graph[26][26];
bool check[26];
bool t;
string sdata;

void dfs(string s)
{
	if (s.size() == sdata.size()) {
		for (int i = 0; i < s.size(); ++i)
			cout << s[i] << (i != s.size() - 1 ? " " : "\n");
		t = true;
		return;
	}

	for (size_t i = 0; i < sdata.size(); ++i)
		if (!check[sdata[i] - 'A']) {
		
			int j = 0;
			for (; j < s.size(); ++j)
				if (graph[sdata[i] - 'A'][s[j] - 'A']) break;

			if (j == s.size()) {
				check[sdata[i] - 'A'] = true;
				dfs(s + sdata[i]);
				check[sdata[i] - 'A'] = false;
			}
		}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int T;
	string str;
	cin >> T;
	cin.ignore();

	while (T--) {

		getline(cin, str);
		sdata.clear();
		t = false;
		memset(graph, false, sizeof(graph));
		memset(check, false, sizeof(check));

		getline(cin, str);
		stringstream ss;
		ss << str;
		while (ss >> str) sdata += str;
		sort(sdata.begin(), sdata.end());

		getline(cin, str);
		ss.clear();
		ss << str;
		while (ss >> str) graph[str[0] - 'A'][str[2] - 'A'] = true;

		dfs("");
		if (!t) cout << "NO\n";
		if (T) cout << "\n";
	}

	return 0;
}

# 參考資料

https://www.larrysprognotes.com/UVa%20-%20872/