# Python DFS Solution

• Feedback for improvement is appreciated!

``````class Node(object):
def __init__(self, value):
self.value = value
self.visited = False
self.onPath = False

def point_to(self, node):

class CyclicGraphException(Exception):
pass

class AlienOrder(object):
def alienOrder(self, words):
try:
graph = self.form_graph(words)
sort = self.topological_sort(graph)
except CyclicGraphException:
return ""
return "".join(sort)

def form_graph(self, words):
graph = {}
for word in words:
for char in word:
if char not in list(graph):
graph[char] = Node(char)
for i in range(len(words) - 1):
word1 = words[i]
word2 = words[i + 1]
for k in range(min(len(word1), len(word2))):
if word1[k] == word2[k]:
k += 1
else:
if graph[word2[k]].point_to(graph[word1[k]]):
raise CyclicGraphException()
break
return graph

def topological_sort(self, graph):
stack = []
for node in graph.values():
if not node.visited:
self.dfs(stack, node)
return stack[::-1]

def dfs(self, stack, node):
node.onPath = True
if next_node.onPath:
raise CyclicGraphException()
if not next_node.visited:
self.dfs(stack, next_node)
stack.append(node.value)
node.visited = True
node.onPath = False

if __name__ == "__main__":
words_1 = ["wrt", "wrf", "er", "ett", "rftt"]
expected_order_1 = "wertf"

words_2 = ["z", "x"]
expected_order_2 = "zx"

words_3 = ["z", "x", "z"]
expected_order_3 = ""

words_4 = ["a", "b", "c", "a"]
expected_order_4 = ""

assert(expected_order_1 == AlienOrder().alienOrder(words_1))
assert(expected_order_2 == AlienOrder().alienOrder(words_2))
assert(expected_order_3 == AlienOrder().alienOrder(words_3))
assert(expected_order_4 == AlienOrder().alienOrder(words_4))
``````

• Solution of count node inbound:

``````from collections import deque

class Node(object):
def __init__(self, value):
self.value = value
self.visited = False
self.onPath = False
self.inbound = 0
self.outbound = 0

def point_to(self, node):

class CyclicGraphException(Exception):
pass

class Solution(object):
class CyclicGraphException(Exception):
pass

def alienOrder(self, words):
"""
:type words: List[str]
:rtype: str
"""
try:
graph = self.form_graph(words)
sort = self.topological_sort(graph)
except CyclicGraphException:
return ""
return "".join(sort)

def form_graph(self, words):
graph = {}
for word in words:
for char in word:
if char not in list(graph):
graph[char] = Node(char)
for i in range(len(words) - 1):
word1 = words[i]
word2 = words[i + 1]
for k in range(min(len(word1), len(word2))):
if word1[k] == word2[k]:
k += 1
else:
if graph[word2[k]].point_to(graph[word1[k]]):
raise CyclicGraphException()
graph[word1[k]].outbound += 1
graph[word2[k]].inbound += 1
break
return graph

def topological_sort(self, graph):
order = []
process_next = deque([])
for k in list(graph):
if graph[k].inbound == 0:
process_next.append(graph[k])
while process_next:
current_node = process_next.popleft()
order.append(current_node.value)