# 269 - Alien Dictionary

## 解法一 - Topological Sort

``````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 : "";
}
};
``````