# Same Topological Sort(DFS) as in Course Schedule

``````class Solution {
public:
string alienOrder(vector<string>& words) {
vector<unordered_set<int> > graph(26);
vector<bool> visited(26, false), onpath(26, false);
string s; // result
bool success = buildGraph(words, graph);
if (!success) return "";
for (int i=0; i<26; ++i) {
if (!graph[i].empty() && dfs_cycle(graph, i, visited, onpath, s)) return "";
}
reverse(s.begin(), s.end());
return s;
}

bool buildGraph(vector<string>&words, vector<unordered_set<int> > &graph) {
for (auto &str : words) {
for (auto c : str) {
graph[c-'a'].insert(c-'a'); //insert itself. otherwise "wxyz", "wxyc" will only output "z, c"; the "w,x,y" will be ignored due to the way the graph is built below
}
}
for (int i=0; i<words.size()-1; ++i) {
int mn = min(words[i].size(), words[i+1].size()), j=0;
for (; j<mn; ++j) {
if (words[i][j]!=words[i+1][j]) {
graph[words[i][j]-'a'].insert(words[i+1][j]-'a'); // find known sequence from input
break;
}
}
if (j==mn && words[i].size() > words[i+1].size()) return false;// this is to handle case "wxyz, wxy" where the order of z and w,x,x is unknown. So return "" eventually
}
return true;
}

bool dfs_cycle(vector<unordered_set<int> >&graph, int node, vector<bool> &visited, vector<bool> & onpath, string &s) {
if (visited[node]) return false;
visited[node]=onpath[node]=true;
for (auto &neig : graph[node]) {
if(node == neig) continue; // for char itself, ignore
if (onpath[neig] || dfs_cycle(graph, neig, visited, onpath, s))
return true;
}
onpath[node]=false;
s+=(char(node+'a'));
return false;
}
};
``````

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