# 4ms C++ Topological Sort using DFS (NOT BFS) -Clean and clear code

• ``````class Solution {
protected:
struct Node
{
char c = 'a', visited = 0;
vector<char> children;
Node (char cc = 'a', char v = 0):c(cc), visited(v){}
};
constexpr static size_t ASIZE = 26;
array<Node *, ASIZE> nodes;
string result;
//return false if order is invalid
bool compare(const string &stra, const string & strb)
{
int i = 0;
for ( ;i < min(stra.size(), strb.size()) && stra[i] == strb[i] ; ++i);
if (i == stra.size())
return true;
if (i == strb.size()) //b is longer than a and all b's chars appear in a
return false;
if (nodes[stra[i] - 'a'] == nullptr)
nodes[stra[i] - 'a'] = new Node{stra[i]};
nodes[stra[i] - 'a']->children.push_back(strb[i]);
if (nodes[strb[i] - 'a'] == nullptr)
nodes[strb[i] - 'a'] = new Node{strb[i]};
return true;
}
//return false if order is invalid
bool dfs(Node * node)
{
if (node == nullptr)
return true;
if (node->visited == 1)
return false;
if (node->visited == 2)
return true;
node->visited = 1;
for (auto c : node->children)
if (!dfs(nodes[c - 'a']))
return false;
node->visited = 2;
result.push_back(node->c);//store by reverse topological order
return true;
}
//return false if order is invalid
bool topologicalSort()
{
for (auto p : nodes)
if (!dfs(p))
return false;
return true;
}
public:
Solution ()
{
fill(begin(nodes), end(nodes), nullptr);
}
~Solution()
{
for (auto p : nodes)
delete p ;
}
string alienOrder(vector<string>& words) {
if (words.empty())
return "";
for (int i = 1; i < words.size(); ++i)
if(!compare(words[i-1], words[i]))
return "";
if (!topologicalSort())
return "";
reverse(result.begin(), result.end());
//handle characters whose order can't be calculated.
for (int i = 0; i < words.size(); ++i)
for(int j = 0 ; j < words[i].size(); ++j)
if (nodes[words[i][j] - 'a'] == nullptr)
{
nodes[words[i][j] - 'a'] = new Node; //mark it
result.push_back(words[i][j]);
}
return result;
}
};``````

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