HardGraphs
Alien Dictionary
Order characters from alien dictionary
Solution Approach
Use Kahn algorithm with in-degree. Start from vertices with 0 in-degree and process in BFS manner.
Implementation
def topologicalSort(vertices, edges):
from collections import defaultdict, deque
graph = defaultdict(list)
in_degree = [0] * vertices
for u, v in edges:
graph[u].append(v)
in_degree[v] += 1
queue = deque([i for i in range(vertices) if in_degree[i] == 0])
result = []
while queue:
u = queue.popleft()
result.append(u)
for v in graph[u]:
in_degree[v] -= 1
if in_degree[v] == 0:
queue.append(v)
return result if len(result) == vertices else []Complexity Analysis
Time Complexity
O(n)Space Complexity
O(1)Complexity
Time:O(n)
Space:O(1)
Asked at
GoogleFacebookAmazon