Topological Order - Kahn's Algorithm

Step 1. we will calculate indegree of all nodes

indegree = kitne log dependent hai mere node pr

package pep.Day44;

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

public class Kahn_Algorithm {

    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));
        }

        kahns(graph);
    }

    public static void kahns(ArrayList<Edge>[] graph) {
        int n = graph.length;
        // first we will find indegree
        int[] indegree = new int[n];
        for (int i = 0; i < n; i++) {
            for (Edge e : graph[i]) {
                indegree[e.nbr]++;
            }
        }

        // jin jin ki indegree 0 hai, unko queue m add kr do
        Queue<Integer> que = new LinkedList<>();
        for (int i = 0; i < indegree.length; i++) {
            if (indegree[i] == 0)
                que.add(i);
        }

        LinkedList<Integer> ans = new LinkedList<>();
        while (!que.isEmpty()) {

            int remove = que.remove();
            ans.addFirst(remove);
            // jisko remove kiya, woh jis jis par dependent hai uski indegree -1 kro
            // if indegree == 0, then again add in queue
            for (Edge e : graph[remove]) {
                if (--indegree[e.nbr] == 0)
                    que.add(e.nbr);
            }
        }
        System.out.println(ans.size() == n ? ans : "cycle is present, topological sort is not possible...");
    }
}