LeetCode 269. 火星词典（拓扑排序）

示例 1：
输入:
[
  "wrt",
  "wrf",
  "er",
  "ett",
  "rftt"
]
输出: "wertf"

示例 2：
输入:
[
  "z",
  "x"
]
输出: "zx"

示例 3：
输入:
[
  "z",
  "x",
  "z"
] 
输出: "" 
解释: 此顺序是非法的，因此返回 ""。
 
提示：
你可以默认输入的全部都是小写字母
若给定的顺序是不合法的，则返回空字符串即可
若存在多种可能的合法字母顺序，请返回其中任意一种顺序即可

class Solution {
public:
    string alienOrder(vector<string>& words) {
        unordered_set<char> allchar;
        for(string& w : words)
        {
        	for(char ch : w)
        		allchar.insert(ch);
        }//记下所有的字符
        unordered_map<char,int> indegree;
        unordered_map<char,unordered_set<char>> graph;
        int n1, n2, n;
        for(int i = 1, j; i < words.size(); ++i)
        {	
        	if(words[i-1] == words[i])
        		continue;
        	n1 = words[i-1].size();
        	n2 = words[i].size();
        	n = min(n1, n2);
        	for(j = 0; j < n; ++j)
        	{
        		if(words[i-1][j] != words[i][j])
        		{	//不相等的第一个构成有向图的边
                    if(!graph.count(words[i-1][j]) || !graph[words[i-1][j]].count(words[i][j]))
        			{   //防止重复添加同一条边 "za","zb","ca","cb"
                        graph[words[i-1][j]].insert(words[i][j]);
                        indegree[words[i][j]]++;
                        indegree[words[i-1][j]] += 0;
                    }
        			break;
        		}
        	}
        	if(j == n && n1 > n2)
        		return "";//前面相等，前者长不行
        }
        queue<char> q;
        for(auto it = indegree.begin(); it != indegree.end(); ++it)
        {
        	if(it->second == 0)//入度为0的入队
        		q.push(it->first);
        }
        string ans;
        while(!q.empty())
        {
        	char ch = q.front();
        	allchar.erase(ch);
        	q.pop();
        	ans += ch;
        	for(auto it = graph[ch].begin(); it != graph[ch].end(); ++it)
        	{
        		if(--indegree[*it] == 0)
        			q.push(*it);
        	}
        }
        if(ans.size() != indegree.size())
        	return "";//有环
        while(allchar.size())
        {	//剩余字符随便放
        	ans += *allchar.begin();
        	allchar.erase(allchar.begin());
        }
        return ans;
    }	
};