import java.util.*;

// Kahn's Algorithm (BFS Topological Sort)
class KahnsAlgorithm {

    // Perform topological sort using Kahn's Algorithm
    public static List<Integer> topologicalSort(int V, List<List<Integer>> adj) {
        List<Integer> topoOrder = new ArrayList<>();
        int[] indegree = new int[V];

        // Step 1: Compute indegree of each node
        // -------------------------------------
        // Time: O(V + E)
        // Every edge (u -> v) contributes +1 to indegree[v]
        for (int u = 0; u < V; u++) {
            for (int v : adj.get(u)) {
                indegree[v]++;
            }
        }

        // Step 2: Initialize queue with nodes having indegree = 0
        // --------------------------------------------------------
        // These have no dependencies and can appear first.
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < V; i++) {
            if (indegree[i] == 0) {
                queue.offer(i);
            }
        }

        // Step 3: BFS traversal (process nodes in dependency order)
        // ---------------------------------------------------------
        // Each node is processed once → O(V)
        // Each edge is removed once → O(E)
        while (!queue.isEmpty()) {
            int node = queue.poll();
            topoOrder.add(node);

            // For every neighbor of current node
            for (int neighbor : adj.get(node)) {
                indegree[neighbor]--; // remove the dependency edge

                // If indegree becomes 0 → can now be processed
                if (indegree[neighbor] == 0) {
                    queue.offer(neighbor);
                }
            }
        }

        // Step 4: Check for cycle
        // ------------------------
        // If topoOrder doesn't include all nodes → graph had a cycle
        if (topoOrder.size() != V) {
            throw new RuntimeException("Graph contains a cycle — topological order not possible!");
        }

        return topoOrder;
    }

    public static void main(String[] args) {
        // Example graph:
        // 5 -> 0 <- 4
        // 5 -> 2 -> 3 -> 1
        // 4 -> 0 -> 1

        int V = 6;
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < V; i++) adj.add(new ArrayList<>());

        // Add edges (directed)
        adj.get(5).add(0);
        adj.get(5).add(2);
        adj.get(4).add(0);
        adj.get(4).add(1);
        adj.get(2).add(3);
        adj.get(3).add(1);

        List<Integer> order = topologicalSort(V, adj);

        System.out.println("Topological Order: " + order);
    }
}