# 題目: UVa 200 - Rare Order

# 題目說明

有一本書，裡面的文字是英文字母，但排列字典序與英文字典序不同
求該書的字典序為何

---

INPUT:
輸入數個字串直到#結束

---

OUTPUT:
輸出子串的字典序排序

# 解題方法

將每兩個字串從第一個字元開始比對，當不同時

1. 將str2push到graph[str1]裡面
2. 將path[str2]設為true
   接著跑dfs將字串照順序加入result

# 參考程式碼

#include <iostream>
#include <vector>
#include <unordered_set>
#include <stack>

using namespace std;

vector<int> graph[26];
stack<char> result;
bool check[26]{}, path[26]{};

void dfs(int num)
{
	check[num] = true;
	for (auto& i : graph[num])
		if (!check[i]) dfs(i);
	result.emplace(num + 'A');
}

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

	string str1, str2;
	cin >> str1;

	unordered_set<int> us;

	while (cin >> str2 && str2 != "#") {		

		for (int i = 0; str1[i] && str2[i]; ++i) {

			us.emplace(str1[i] - 'A');
			us.emplace(str2[i] - 'A');

			if (str1[i] != str2[i]) {
				graph[str1[i] - 'A'].emplace_back(str2[i] - 'A');
				path[str2[i] - 'A'] = true;
				break;
			}
		}

		str1 = str2;
	}

	for (auto& i : us)
		if (!path[i]) dfs(i);

	while (!result.empty()) cout << result.top(), result.pop();
	cout << "\n";

	return 0;
}

# 參考資料

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