Topological Order - DFS

 

package pep.Day42;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Topological_Order {

    static class Edge {
        int src;
        int nbr;

        Edge(int src, int nbr) {
            this.src = src;
            this.nbr = nbr;
        }
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int vtces = Integer.parseInt(br.readLine());
        ArrayList<Edge>[] graph = new ArrayList[vtces];
        for (int i = 0; i < vtces; i++) {
            graph[i] = new ArrayList<>();
        }

        int edges = Integer.parseInt(br.readLine());
        for (int i = 0; i < edges; i++) {
            String[] parts = br.readLine().split(" ");
            int v1 = Integer.parseInt(parts[0]);
            int v2 = Integer.parseInt(parts[1]);
            graph[v1].add(new Edge(v1, v2));
            // directed graph hai to isko comment kr denge
            // graph[v2].add(new Edge(v2, v1));
        }
        topologicalOrder(vtces, graph);
    }

    public static void topologicalOrder(int n, ArrayList<Edge>[] graph) {
        boolean[] visited = new boolean[n];
        // topological sort ko arrayList me fill krte hain
        ArrayList<Integer> ans = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            if (visited[i] == false) {
                // dfs ka method likhna hai, which will tell konse order me mere nodes add honge
                // i.e. post order
                topoDfs(graph, i, visited, ans);
            }
        }

        System.out.println(ans);
    }

    private static void topoDfs(ArrayList<Edge>[] graph, int src, boolean[] visited, ArrayList<Integer> ans) {

        visited[src] = true;
        for (Edge e : graph[src]) {
            if (!visited[e.nbr]) {
                topoDfs(graph, e.nbr, visited, ans);
            }
        }
        // recursion ke call lgane ke baad add krenge i.e. post order
        ans.add(src);

    }

}