toposort

import java.util.*;

public class Solution {

    // Helper method for DFS-based Topological Sort
    private static void dfsTopoSort(List<List<Integer>> adj, int node, boolean[] visited, List<Integer> result) {
        visited[node] = true;

        for (int neighbor : adj.get(node)) {
            if (!visited[neighbor]) {
                dfsTopoSort(adj, neighbor, visited, result);
            }
        }

        result.add(node); // Add to result list after exploring all neighbors (post-order)
    }

    // Main method to perform Topological Sort
    public static List<Integer> topoSort(int V, int[][] edges) {
        // Step 1: Build the adjacency list
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < V; i++) {
            adj.add(new ArrayList<>());
        }

        for (int[] edge : edges) {
            adj.get(edge[0]).add(edge[1]);
        }

        // Step 2: Perform DFS for topological sort
        boolean[] visited = new boolean[V];
        List<Integer> result = new ArrayList<>();

        for (int i = 0; i < V; i++) {
            if (!visited[i]) {
                dfsTopoSort(adj, i, visited, result);
            }
        }

        // Step 3: Reverse the result to get the correct topological order
        Collections.reverse(result);
        return result;
    }
}