Topological sort

"""
Topological sorting for a directed graph is a linear ordering of its vertices such that for every directed edge UV from vertex U to vertex V, U comes before V in the ordering. Topological Sorting is possible if and only if the graph has no directed cycles, that is, if it is a Directed Acyclic Graph (DAG).

One common way to perform a topological sort is to use Kahn's Algorithm, which involves iteratively removing nodes with no incoming edges and removing their outgoing edges from the graph.
"""
from collections import deque

def topological_sort(graph):
    # Calculate in-degree (number of incoming edges) for each node
    in_degree = {u: 0 for u in graph}  # Initialize in-degree as 0 for all vertices
    for u in graph:
        for v in graph[u]:
            in_degree[v] += 1

    # Queue for all nodes with no incoming edge
    queue = deque([u for u in graph if in_degree[u] == 0])

    top_order = []  # List to store the topological order

    while queue:
        u = queue.popleft()  # Choose the vertex with no incoming edges
        top_order.append(u)

        # Decrease in-degree by 1 for all its neighboring nodes
        for v in graph[u]:
            in_degree[v] -= 1
            # If in-degree becomes zero, add it to the queue
            if in_degree[v] == 0:
                queue.append(v)

    # Check if there was a cycle
    if len(top_order) != len(graph):
        return "The graph has at least one cycle and cannot be topologically sorted."
    else:
        return top_order

# Example usage
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

print(topological_sort(graph))
# Output: ['A', 'B', 'C', 'D', 'E', 'F'] or any other order that satisfies the topological order conditions