# Simple top sort, Kahn's algorithm

• ``````class Solution {
public:
string alienOrder(vector<string>& words) {
vector<vector<int>> g(256);
vector<int> indegree(256, 0);
for(int i=1; i < words.size(); i++){
string w1 = words[i-1];
string w2 = words[i];
for(int j=0; j<min(w1.length(), w2.length()); j++){
if(w1[j]!=w2[j]){
g[w1[j]].push_back(w2[j]);
indegree[w2[j]]++;
break;
}
}
}

char res[256];
int resPos=0;
queue<int> leaves;
set<int> seen;
for(int i=0; i<words.size(); i++){
for(int j=0; j<words[i].length(); j++){
int c = words[i][j];
if(seen.count(c) != 0) continue;
seen.insert(c);

if(indegree[words[i][j]] == 0){
leaves.push(words[i][j]);
}
}
}

while(!leaves.empty()){
int c = leaves.front();
leaves.pop();
res[resPos++] = ((char)c);

for(int i=0; i<g[c].size(); i++){
int y = g[c][i];
indegree[y]--;
if(indegree[y] == 0){
leaves.push(y);
}
}
}

if(resPos < seen.size()) return ""; // graph is not a DAG

res[resPos] = '\0';
return string(res);
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.