# 269\. Alien Dictionary -- topological sort

topological sort, aka, straightening a graph to a line


[picture source](https://www.techiedelight.com/kahn-topological-sort-algorithm/)

- method 1: BFS aka Kahn's algorithm
- method 2: DFS
- color with grey then black
- kind of backtracking with early return

"""
BFS
"""
class Solution:
    def alienOrder(self, words: List[str]) -> str:
        G=collections.defaultdict(set) # Graph
        in_degree={c:0 for word in words for c in word }
        for former_word,latter_word in zip(words,words[1:]):
            for c,d in zip(former_word,latter_word):
                if c!=d:
                    if d not in G[c]:
                        G[c].add(d) # c < d
                        in_degree[d]+=1
                    break
            else:
                # e.g., 
                if len(former_word)>len(latter_word):
                    return ""
                
        ans=[]
        q=collections.deque([c for c in in_degree if in_degree[c]==0])
        while q:
            c=q.popleft()
            ans.append(c)
            for d in G[c]: # c < d
                in_degree[d]-=1
                if in_degree[d]==0:
                    q.append(d)
        if len(ans) < len(in_degree):
            return ""   
        return ''.join(ans)
"""
DFS
"""
class Solution:
    def alienOrder(self, words: List[str]) -> str:
        reversed_adj_list = {c : [] for word in words for c in word}
        
        for first_word, second_word in zip(words,words[1::]):
            for c,d in zip(first_word,second_word):
                if c!=d:
                    reversed_adj_list[d].append(c) #  c < d
                    break
            else:
                if len(first_word)>len(second_word):
                    return ''
                
        seen={} # once and twice
        ans=[]
        def dfs(node):
            if node in seen:
                if seen[node]=="grey":
                    return False # we detect a loop
                else: # black
                    return True
            seen[node]="grey"
            for next_node in reversed_adj_list[node]:
                # all next_node < node
                if dfs(next_node)==False: # we detect a loop
                    return False
                
            seen[node]="black"
            ans.append(node)
            return True
        
        if not all(dfs(node) for node in reversed_adj_list):
            return ''
        return ''.join(ans)
"""
DFS
"""
class Solution:
    def alienOrder(self, words: List[str]) -> str:
        adj_list = {c : [] for word in words for c in word}
        
        for first_word, second_word in zip(words,words[1::]):
            for c,d in zip(first_word,second_word):
                if c!=d:
                    adj_list[c].append(d) #  c < d
                    break
            else:
                if len(first_word)>len(second_word):
                    return ''
                
        seen={} # once:grey and twice:black
        ans=[]
        def dfs(node):
            if node in seen:
                if seen[node]=="grey":
                    return False # we detect a loop
                else: # black
                    return True
            seen[node]="grey"
            for next_node in adj_list[node]:
                # all next_node < node
                if dfs(next_node)==False: # we detect a loop
                    return False
            seen[node]="black"
            ans.append(node)
            return True
        
        if not all(dfs(node) for node in adj_list):
            return ''
        return ''.join(reversed(ans))  # or you can use # return ''.join(ans)[::-1]

## topological sort

Leetcode
https://leetcode.com/problems/alien-dictionary/solution/

Leetcode CN
https://leetcode.cn/problems/alien-dictionary/solution/huo-xing-ci-dian-by-leetcode-solution-nr0l/

### Kahn's Algorithm -- BFS -- indegree

[picture source](https://www.interviewkickstart.com/learn/kahns-algorithm-topological-sorting)

For indegree==0, a node good to be a global source/start.
Collect it, detach it from the graph, and remove the edges.

### DFS -- outdegree

For outdegree==0, a node to be a global destination/end.

So, the leaf node when doing DFS is safe to be a global destination/end.

When firstly arriving, mark it as GREY.
When bouncing back, mark it as BLACK.


def dfs(node):
    if node in seen:
        if seen[node] == "GREY":
            return False # We detect a loop
        else: # BLACK # It is already fully explored.
            return True
    seen[node] = "GREY"
    for next_node in adj_list[node]:
        if dfs(next_node) == False: # We detect a loop.
            return False  # Report this to the caller.
    seen[node] = "BLACK"
    ans.append(node)  # Note that the order is reversed.
    return True