[算法题]火星词典
题目链接：火星词典
用拓扑排序求解：
1. 用 unordered_map<char, unordered_map<char, bool>> 保存字母的顺序关系，key 表示某个字母，val 表示排在 key 之后的字母的集合，已经记录出现过置为 true
2. 用 unordered_map<char, int> 保存入度，需要初始化，将出现过的字母设置 val 为 0
3. 需要固定一个字符串与其后每个字符串做比较，两个比较的字符串同时从下标 0 开始比较每个字母，不相同时则为 a -> b，b的入度++，更新后 break，循环到遍历结束
4. 定义一个队列，将入度为 0 的字母入队
5. 做一次 bfs
6. 判断是否有环并依此输出相应结果
题解代码：
class Solution
{
public:string alienOrder(vector<string>& words) {string res; //保存结果unordered_map<char, unordered_map<char, bool>> edges; //保存点与点的连接关系unordered_map<char, int> in; //保存入度//初始化入度for(const auto& s : words){for(const auto& c : s){if(!in.count(c)){in[c] = 0;}}}for(int i = 0; i < words.size() - 1; ++i){for(int j = i + 1; j < words.size(); ++j){for(int k = 0; k < words[i].size(); ++k){//遇到"abc"-"ab"这种对比情况,直接返回""if(k == words[j].size()){return "";}//建立点与点的顺序关系if (words[i][k] != words[j][k]){//如果已经建立过关系则无需重复建立if (!edges[words[i][k]][words[j][k]]){edges[words[i][k]][words[j][k]] = true;in[words[j][k]]++; //更新入度}break;}}}}queue<char> q;//将入度为0的点添加到队列for(const auto& [k, v] : in){if(!v){q.push(k);}}//bfswhile(!q.empty()){char ch = q.front();q.pop();res += ch;for(const auto& [k, _] : edges[ch]){if(--in[k] == 0){q.push(k);}}}//判断是否存在环for(const auto& [_, v] : in){if(v){return "";}}return res;}
};