There is a new alien language which uses the latin alphabet. However, the order among letters are unknown to you. You receive a list of words from the dictionary, wherewords are sorted lexicographically by the rules of this new language. Derive the order of letters in this language.

For example,
Given the following words in dictionary,

[
  "wrt",
  "wrf",
  "er",
  "ett",
  "rftt"
]

The correct order is: "wertf".

Note:

1. You may assume all letters are in lowercase.
2. If the order is invalid, return an empty string.
3. There may be multiple valid order of letters, return any one of them is fine.

For each two adjacent strings str1 and str2, find the first mismatch character str1[i] and str2[i]. Add an directed edge from str1[i] to str2[i] in the graph.

Topological sort the graph.

If the graph contains circle or has no nodes with no incoming edges, return empty string, which means error.

//Step 1. construct the directed graph
//Step 2. Topological sort 

//What is the order of "wr" and "wrd"? 
class Node{
private:
    char c;
    int incomingNum;
    
public:
    unordered_map<char, Node *> next;
    Node(char c):c(c), incomingNum(0){}
    Node(): incomingNum(0){}//for unordered_map usage
    void addIncomingNum(){
        incomingNum++;
    }
    void minusIncomingNum(){
        incomingNum--;
    }
    int getIncomingNum(){
        return incomingNum;
    }
    char getC(){
        return c;
    }
};
class Solution {
public:
    string alienOrder(vector<string>& words) {
        string ans;
        unordered_map<char, int> letters;
        unordered_map<char, Node> graph;
        if(words.size() == 0) return ans;
        //collect all availiable letters
        for(auto it = words.begin(); it != words.end(); it++){
            for(auto is = (*it).begin(); is != (*it).end(); is++){
                letters[*is] = 1;
            }
        }
        //construct the directed graph
        for(size_t i = 0; i + 1 < words.size(); i++){
            string str1 = words[i];
            string str2 = words[i + 1];
            for(size_t j = 0; j < min(str1.size(), str2.size()); j++){
                if(str1[j] != str2[j]){
                    //first mismatch char
                    char thisc = str1[j];
                    char nextc = str2[j];
                    if(graph.find(thisc) == graph.end()){
                        //meet a new node
                        graph[thisc] = Node(thisc);
                    }
                    if(graph.find(nextc) == graph.end()){
                        //meet a new node
                        graph[nextc] = Node(nextc);
                    }
                    if(graph[thisc].next.find(nextc) == graph[thisc].next.end()){
                        //edge not exsit before
                        graph[thisc].next[nextc] = &graph[nextc];
                        graph[nextc].addIncomingNum();
                    }
                    break;//BUG HERE, remember to break
                }
            }
            //code would run into this line if str1 looks like "asfd" and str2 looks like "asfds"
            
        }
        //Topologically sort the graph
        //find all nodes with no incoming edges
        queue<Node *> startNodes;
        for(auto it = graph.begin(); it != graph.end(); it++){
            if(it->second.getIncomingNum() == 0){
                startNodes.push(&(it->second));
            }
        }
        if(startNodes.size() == 0 && graph.size() > 0){
            return "";//error, circle in the graph
        }
        //Topological sort
        while(startNodes.empty() != true){
            Node * p = startNodes.front();
            startNodes.pop();
            //push current node to result string
            ans.push_back(p->getC());
            
            for(auto it = p->next.begin(); it != p->next.end(); it++){
                Node * np = it->second;
                np->minusIncomingNum();
                if(np->getIncomingNum() == 0){
                    startNodes.push(np);
                }
            }
        }
        //Check if there are edges in graph, circle exist
        for(auto it = graph.begin(); it != graph.end(); it++){
            if(it->second.getIncomingNum() != 0){
                return "";
            }
        }
        for(size_t i = 0; i < ans.size(); i++){
            letters[ans[i]] = 0;
        }
        for(auto it = letters.begin(); it != letters.end(); it++){
            if(it->second == 1){
                //letter appeared in dict but not in the graph
                ans.push_back(it->first);
            }
        }
        return ans;
    }
};