toposort_scratch

class Soln:
    def webappdeployment(self, prereqmap):
        visitset = set()                 
        ordered_res = []      
        
        def dfs(webapp):
            if prereqmap[webapp]==[]:    
                if webapp not in ordered_res:
                    ordered_res.append(webapp)
                return True
            if webapp in visitset:  # Cycle 
                return False
            
            visitset.add(webapp)      
            for app in prereqmap[webapp]:
                if not dfs(app):       
                    return False
            
            if webapp not in ordered_res:
                ordered_res.append(webapp)
            visitset.remove(webapp)
            prereqmap[webapp]=[]
            return True
        
        for webapp in prereqmap:
            if not dfs(webapp):  
                return []  
        return ordered_res  

obj = Soln()
res = obj.webappdeployment({'A': ['B'], 'B': ['C', 'D', 'E'], 'C': ['F'], 'D': ['F'], 'E': [], 'F':[]})
print(res)  # Expected output: ['F', 'C', 'D', 'E', 'B', 'A']
print("microsoft")