Topological Sort

Write a program to implement topological sort.

Example 1:

Input: n=6 , edges={{1,2},{2,3},{4,3},{5,3},{6,2}}
Output: 1 4 5 6 2 3

Approach:

Java

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;

public class TopologicalSort {
    // visited list
    public static ArrayList<Integer> visited = new ArrayList<>();
    // traversal list
    public static ArrayList<Integer> ans = new ArrayList<>();
    // store the indegree of all the nodes
    static HashMap<Integer, Integer> indegre = new HashMap<>();

    public static void main(String[] args) {
        // Adjacency Lists
        ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
        int v = 7;
        for (int i = 0; i < v; i++)
            adj.add(new ArrayList<>());

        addEdge(adj, 1, 2);
        addEdge(adj, 2, 3);
        addEdge(adj, 4, 3);
        addEdge(adj, 5, 3);
        addEdge(adj, 6, 2);
        // bfs calling
        topologicalSort(adj, v);
        // print traversal list
        ans.forEach(i -> System.out.print(i + " "));
    }

    private static void topologicalSort(
                ArrayList<ArrayList<Integer>> adj, int v) {
        // create queue
        Queue<Integer> queue = new LinkedList<>();
        // if indegree of the vertex is
        // zero then insert into the queue
        for (int i = 1; i < v; i++) {
            if (indegre.get(i) == null) {
                queue.add(i);
            }
        }
        // Iterate till the queue is not empty
        while (!queue.isEmpty()) {
            // current node from the queue
            int curr = queue.poll();
            // insert the current data into the result
            ans.add(curr);
            // iterate for all the adjacency
            // of the cuurent node
            for (int node : adj.get(curr)) {
                // decrease the indegre of the node
                indegre.put(node, indegre.getOrDefault(node, 0) - 1);
                // if indegree becomes zero
                // add into the queue
                if (indegre.get(node) == null
                             || indegre.get(node) == 0) {
                    queue.add(node);
                }
            }
        }

    }

    /**
     * @Desc : Method used for add edges
     * @param u
     * @param v
     */

    private static void addEdge(ArrayList<ArrayList<Integer>> g,
                     int u, int v) {
        // directed graph
        g.get(u).add(v);
        // check and add indegree
        indegre.put(v, indegre.getOrDefault(v, 0) + 1);
    }

}

C++

#include <bits/stdc++.h>
using namespace std;
//ajdacency list to
//store all the edges
vector<int> arr[100001];
//store the indegree of 
//all the nodes
int indegre[100001];
//function to add the edge 
void addEdge(int u,int v)
{
    //directed graph
    arr[u].push_back(v);
    //increment the indegee
    indegre[v]++;
}
//funtion to find the topological
//sort of the graph
vector<int>  topologicalSort(int n)
{
    //queue to store the nodes
    //of the graph
    queue<int> q;
    //store the result 
    vector<int> res; 
    //if indegre of the vertex is
    //zero  then insert into the
    //queue
    for(int i=1;i<=n;i++)
       {
           if(indegre[i]==0)
              {
                  q.push(i);
              }
       }
    //iterate till the queue is
    //not empty
    while(!q.empty())
     {
         //current node from the queue
        int curr=q.front();
        //insert the current data into
        //the result
        res.push_back(curr);
        //popped from the queue
        q.pop();
        //iterate for all the adjacency
        //of the cuurent node
        for(int node:arr[curr])
          {
              //decrease the indegre of the node
              indegre[node]--;
               //if indegree becomes zero 
               //add into the queue
              if(indegre[node]==0)
                 q.push(node);
           }
     }
    //return the topological sort
  return res;
}
int main()
{
    int n=6;
    int edges=5;
    addEdge(1,2);
    addEdge(2,3);
    addEdge(4,3);
    addEdge(5,3);
    addEdge(6,2);
    vector<int> topo=topologicalSort(n);
    cout<<"Topological Sort is ";
    for(int i=0;i<n;i++)
      cout<<topo[i]<<" ";
    return 0;
}