# Python topological sort w/o BFS/GFS

• We do not need a DFS or BFS to detect if there is a cycle, because if the graph stop shrinking before all nodes are removed, it indicates that solution doesn't exist (a cycle in the graph)

``````class Node(object):
def __init__(self):
self.IN = set()
self.OUT = set()

class Solution(object):
def alienOrder(self, words):
# find out nodes
graph = {}
for word in words:
for letter in word:
if letter not in graph:
graph[letter] = Node()

# find out directed edges (from StefanPochmann)
for pair in zip(words, words[1:]):
for a, b in zip(*pair):
if a != b:
break

# topo-sort
res = ""
while graph:
oldlen = len(graph)

for key in graph:
if not graph[key].IN:   # to remove this
for key2 in graph[key].OUT:
graph[key2].IN.remove(key)
del graph[key]
res += key
break

if oldlen == len(graph): # if shrinking stops, solution doesn't exist
return ""
oldlen = len(graph)
return res``````

• Just revisited and had cleaner code

``````class Node(object):
def __init__(self):
self.IN = set()
self.OUT = set()

class Solution(object):
def alienOrder(self, words):
# initialization
allnodes, graph, res = set("".join(words)), {}, ""
for i in allnodes:
graph[i] = Node()

# build the graph
for i in range(len(words)-1):
for j in zip(words[i], words[i+1]):
if j[0] != j[1]:
break

# topo-sort
while allnodes:
buff = set([i for i in allnodes if graph[i].OUT and not graph[i].IN])
if not buff:
return res + "".join(allnodes) if not [i for i in allnodes if graph[i].IN] else "" # have solution if no connected node
res += "".join(buff)
allnodes -= buff
for i in allnodes:
graph[i].IN -= buff
return res``````

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