# 269 - Alien Dictionary

解法一 - Topological Sort

這題跟上面不一樣的地方只在於如何 build graph，剩下的東西就都一樣：

class Solution {
public:
    string alienOrder(vector<string>& words) {
        // Init the graph
        unordered_map<char, int> inDegree;
        unordered_map<char, vector<char>> graph;
        for (auto word : words) {
            for (char character : word) {
                inDegree[character] = 0;
                graph[character] = vector<char>();
            }
        }

        // Build the graph
        for (int i = 0; i < words.size() - 1; i++) {
            // find ordering of characters from adjacent words
            string w1 = words[i], w2 = words[i + 1]; 

            for (int j = 0; j < min(w1.length(), w2.length()); j++) {
                char parent = w1[j], child = w2[j];
                if (parent != child) {             // if the two characters are different
                    graph[parent].push_back(child);  // put the child into it's parent's list   
                    inDegree[child]++;               // increment child's inDegree
                    break;  // only the first different character between the two words will help us 
                }
            }
        }

        // Find sources
        queue<char> sources;
        for(auto& p: inDegree) {
            if(p.second == 0) {
                sources.push(p.first);
            }
        }

        // Start toppological sort
        string order;
        while(!sources.empty()) {
            char cur = sources.front();
            sources.pop();

            order += cur;

            for(auto& child: graph[cur]) {
                if(--inDegree[child] == 0) {
                    sources.push(child);
                }
            }
        }

        return order.length() == inDegree.size() ? order : "";
    }
};