How to get all the solutions of topological sorting

Hi everyone I was trying to solve this problem and I realized that it wants to get all the solutions of topological sorting problem, I know how to get only one possible solution and this is my code

static ArrayList<Integer> [] arr;  
static int visited [];
static Stack<Integer> a = new Stack<Integer>();
static boolean flag=false;

public static void graphcheck(int node){  //method to check if there is a cycle in the graph
    visited[node] = 2;
    for(int i=0;i<arr[node].size();i++){
        int u =arr[node].get(i);
        }else if(visited[u]==2){
    visited[node] = 1;

public static void dfs2(int node){            //method to get one possible topological sort which I want to extend to get all posibilites
    visited[node] = 1;
    for(int i=0;i<arr[node].size();i++){
        int u =arr[node].get(i);

public static void main(String[] args) throws NumberFormatException, IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(;
    int tc = Integer.parseInt(br.readLine());
    for(int k=0;k<tc;k++){

        String h[]= br.readLine().split(" ");
        int n= h.length;
        arr=new ArrayList[n];
        visited = new int[n];
        for( int i = 0; i < n; i++) {
            arr[ i] = new ArrayList<Integer>();
        String q[]=br.readLine().split(" ");
        int y=q.length;
        for(int i=0;i<y;i++){
            int x=0;
            int z=0;
            for(int j=0;j<n;j++){
                }else if(q[i].charAt(2)==h[j].charAt(0)){
        for(int i=0;i<n;i++){
        Arrays.fill(visited, 0);
        for(int i=0;i<n;i++){
        int z= a.size();
        for(int i=0;i<z;i++){
            int x =a.pop();
            System.out.print(h[x]+" ");



A potential way would be to modify the algorithm specified by Khan, (1962), in which a topological sort is calculated using the following algorithm:

L ← Empty list that will contain the sorted elements

S ← Set of all nodes with no incoming edges

while S is non-empty do

   remove a node n from S

   insert n into L

   for each node m with an edge e from n to m do

      remove edge e from the graph

       if m has no other incoming edges then

           insert m into S

if graph has edges then

   return error (graph has at least one cycle)


   return L (a topologically sorted order)

This calculates one topological sort, in order to generate all possible sorts. To get all possible sorts, you could think of the result as a tree, where the root is the first node, and each child of a node is one of the next values. Given a graph:

    1 -> 3 -> 8 
    |    |    |
    |    v    |
    |    7    |
    |        |
    |      _ v
    +--> 5 -> 9

The tree might look like:

      3   5
     /|  |
    7 8 9 9
    | |
    9 9

However, after re-reading your problem:

Given a list of variable constraints of the form A < B, you are to write a program that prints all orderings of the variables that are consistent with the constraints. For example, given the contraints A < B and A < C there are two orderings of the variables A, B and C that are consistent with these constraints: ABC and ACB.

I don’t believe this solution will provide you with the answers you are looking for, but you are more than welcome to try and implement it.

Also check out this algorithm.


I was going to refrain from posting this after re-reading your problem, however I decided against it, as this information may be useful to you.

Good luck.

Leave a Reply

Your email address will not be published. Required fields are marked *